Open Problem Garden

Pentagon problem ★★★

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)}$ .

Keywords: induced subgraph

Posted by mdevos
updated March 18th, 2007

add new comment

Graph Theory » Algebraic G.T.

Hamiltonian paths and cycles in vertex transitive graphs ★★★

Author(s): Lovasz

Problem Does every connected vertex-transitive graph have a Hamiltonian path?

Keywords: cycle; hamiltonian; path; vertex-transitive

Posted by mdevos
updated March 18th, 2007

add new comment

Graph Theory » Algebraic G.T.

57-regular Moore graph? ★★★

Author(s): Hoffman; Singleton

Question Does there exist a 57-regular graph with diameter 2 and girth 5?

Keywords: cage; Moore graph

Posted by mdevos
updated March 18th, 2007

add new comment

login-create3

add new comment

Graph Theory » Graph Algorithms

The stubborn list partition problem ★★

Author(s): Cameron; Eschen; Hoang; Sritharan

Problem Does there exist a polynomial time algorithm which takes as input a graph $G$ and for every vertex $v \in V(G)$ a subset $\ell(v)$ of $\{1,2,3,4\}$ , and decides if there exists a partition of $V(G)$ into $\{A_1,A_2,A_3,A_4\}$ so that $v \in A_i$ only if $i \in \ell(v)$ and so that $A_1,A_2$ are independent, $A_4$ is a clique, and there are no edges between $A_1$ and $A_3$ ?