Open Problem Garden

Graph Theory » Coloring » Vertex coloring

Reed's omega, delta, and chi conjecture ★★★

Author(s): Reed

For a graph $G$ , we define $\Delta(G)$ to be the maximum degree, $\omega(G)$ to be the size of the largest clique subgraph, and $\chi(G)$ to be the chromatic number of $G$ .

Conjecture $\chi(G) \le \ceil{\frac{1}{2}(\Delta(G)+1) + \frac{1}{2}\omega(G)}$ for every graph $G$ .

Keywords: coloring

Posted by mdevos
updated September 24th, 2007

2 comments

Seymour's self-minor conjecture ★★★

Author(s): Seymour

Conjecture Every infinite graph is a proper minor of itself.

Keywords: infinite graph; minor

Posted by mdevos
updated April 15th, 2010

2 comments

Planar graphs

Graph Theory » Topological G.T. » Drawings

Universal point sets for planar graphs ★★★

Author(s): Mohar

We say that a set $P \subseteq {\mathbb R}^2$ is $n$ -universal if every $n$ vertex planar graph can be drawn in the plane so that each vertex maps to a distinct point in $P$ , and all edges are (non-intersecting) straight line segments.