Open Problem Garden

The Two Color Conjecture ★★

Conjecture If $G$ is an orientation of a simple planar graph, then there is a partition of $V(G)$ into $\{X_1,X_2\}$ so that the graph induced by $X_i$ is acyclic for $i=1,2$ .

Keywords: acyclic; digraph; planar

Posted by mdevos
updated May 31st, 2007

1 comment

Pentagon problem ★★★

Author(s): Nesetril

Question Let $G$ be a 3-regular graph that contains no cycle of length shorter than $g$ . Is it true that for large enough~ $g$ there is a homomorphism $G \to C_5$ ?

Keywords: cubic; homomorphism

Posted by Robert Samal
updated March 24th, 2007

add new comment

Graph Theory » Hypergraphs

Conjecture Let $H$ be an $r$ -uniform $r$ -partite hypergraph. If $\nu$ is the maximum number of pairwise disjoint edges in $H$ , and $\tau$ is the size of the smallest set of vertices which meets every edge, then $\tau \le (r-1) \nu$ .

Keywords: hypergraph; matching; packing

Posted by mdevos
updated March 19th, 2007

add new comment

Graph Theory » Basic G.T.

Graham's conjecture on tree reconstruction ★★

Author(s): Graham

Problem for every graph $G$ , we let $L(G)$ denote the line graph of $G$ . Given that $G$ is a tree, can we determine it from the integer sequence $|V(G)|, |V(L(G))|, |V(L(L(G)))|, \ldots$ ?

Keywords: reconstruction; tree

Posted by mdevos
updated January 16th, 2013

5 comments

Theoretical Comp. Sci. » Complexity

Subset-sums equality (pigeonhole version) ★★★

Author(s):

Problem Let $a_1,a_2,\ldots,a_n$ be natural numbers with $\sum_{i=1}^n a_i < 2^n - 1$ . It follows from the pigeon-hole principle that there exist distinct subsets $I,J \subseteq \{1,\ldots,n\}$ with $\sum_{i \in I} a_i = \sum_{j \in J} a_j$ . Is it possible to find such a pair $I,J$ in polynomial time?

Keywords: polynomial algorithm; search problem

Posted by mdevos
updated July 16th, 2007

10 comments

Graph Theory » Extremal G.T.

The Erdös-Hajnal Conjecture ★★★

Author(s): Erdos; Hajnal

Conjecture For every fixed graph $H$ , there exists a constant $\delta(H)$ , so that every graph $G$ without an induced subgraph isomorphic to $H$ contains either a clique or an independent set of size $|V(G)|^{\delta(H)}$ .