Open Problem Garden

McDiarmid, Colin

Graph Theory » Coloring » Vertex coloring

Weighted colouring of hexagonal graphs. ★★

Conjecture There is an absolute constant $c$ such that for every hexagonal graph $G$ and vertex weighting $p:V(G)\rightarrow \mathbb{N}$ , $\chi(G,p) \leq \frac{9}{8}\omega(G,p) + c$

Keywords:

Posted by fhavet
updated March 13th, 2013

add new comment

Graph Theory » Coloring » Vertex coloring

Colouring the square of a planar graph ★★

Author(s): Wegner

Conjecture Let $G$ be a planar graph of maximum degree $\Delta$ . The chromatic number of its square is

$7$

$\Delta =3$

$\Delta+5$

$4\leq\Delta\leq 7$

$\left\lfloor\frac32\,\Delta\right\rfloor+1$

$\Delta\ge8$

Keywords:

Posted by fhavet
updated March 13th, 2013

add new comment | 1 attachment

Wegner

Graph Theory » Coloring » Vertex coloring

List chromatic number and maximum degree of bipartite graphs ★★

Author(s): Alon

Conjecture There is a constant $c$ such that the list chromatic number of any bipartite graph $G$ of maximum degree $\Delta$ is at most $c \log \Delta$ .

Keywords:

Posted by fhavet
updated March 12th, 2013

add new comment

Graph Theory » Basic G.T. » Cycles

Hamilton decomposition of prisms over 3-connected cubic planar graphs ★★

Author(s): Alspach; Rosenfeld

Conjecture Every prism over a $3$ -connected cubic planar graph can be decomposed into two Hamilton cycles.

Keywords:

Posted by fhavet
updated March 12th, 2013

add new comment

Graph Theory » Hypergraphs

Turán's problem for hypergraphs ★★

Author(s): Turan

Conjecture Every simple $3$ -uniform hypergraph on $3n$ vertices which contains no complete $3$ -uniform hypergraph on four vertices has at most $\frac12 n^2(5n-3)$ hyperedges.

Conjecture Every simple $3$ -uniform hypergraph on $2n$ vertices which contains no complete $3$ -uniform hypergraph on five vertices has at most $n^2(n-1)$ hyperedges.