Open Problem Garden

Mapping planar graphs to odd cycles ★★★

Author(s): Jaeger

Conjecture Every planar graph of girth $\ge 4k$ has a homomorphism to $C_{2k+1}$ .

Keywords: girth; homomorphism; planar graph

Posted by mdevos
updated June 24th, 2007

add new comment

girth

Graph Theory » Topological G.T. » Coloring

5-local-tensions ★★

Author(s): DeVos

Conjecture There exists a fixed constant $c$ (probably $c=4$ suffices) so that every embedded (loopless) graph with edge-width $\ge c$ has a 5-local-tension.

Keywords: coloring; surface; tension

Posted by mdevos
updated June 22nd, 2007

add new comment

Graph Theory » Algebraic G.T.

Laplacian Degrees of a Graph ★★

Author(s): Guo

Conjecture If $G$ is a connected graph on $n$ vertices, then $c_k(G) \ge d_k(G)$ for $k = 1, 2, \dots, n-1$ .

Keywords: degree sequence; Laplacian matrix

Posted by Robert Samal
updated February 29th, 2008

2 comments

Concavity of van der Waerden numbers ★★

Author(s): Landman

For $k$ and $\ell$ positive integers, the (mixed) van der Waerden number $w(k,\ell)$ is the least positive integer $n$ such that every (red-blue)-coloring of $[1,n]$ admits either a $k$ -term red arithmetic progression or an $\ell$ -term blue arithmetic progression.