Open Problem Garden

Graph Theory » Topological G.T. » Coloring

Bounded colorings for planar graphs ★★

Author(s): Alon; Ding; Oporowski; Vertigan

Question Does there exists a fixed function $f : {\mathbb N} \rightarrow {\mathbb N}$ so that every planar graph of maximum degree $d$ has a partition of its vertex set into at most three sets $\{V_1,V_2,V_3\}$ so that for $i=1,2,3$ , every component of the graph induced by $V_i$ has size at most $f(d)$ ?

Keywords: coloring; partition; planar graph

Posted by mdevos
updated May 23rd, 2007

add new comment

Ding, Guoli

Oporowski, Bogdan

Number Theory » Combinatorial N.T.

Gao's theorem for nonabelian groups ★★

Author(s): DeVos

For every finite multiplicative group $G$ , let $s(G)$ ( $s'(G)$ ) denote the smallest integer $m$ so that every sequence of $m$ elements of $G$ has a subsequence of length $>0$ (length $|G|$ ) which has product equal to 1 in some order.

Conjecture $s'(G) = s(G) + |G| - 1$ for every finite group $G$ .

Keywords: subsequence sum; zero sum

Posted by mdevos
updated May 23rd, 2007

add new comment

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