Graph Theory » Coloring » Vertex coloring

Alon-Saks-Seymour Conjecture ★★★

Author(s): Alon; Saks; Seymour

Conjecture   If $ G $ is a simple graph which can be written as an union of $ m $ edge-disjoint complete bipartite graphs, then $ \chi(G) \le m+1 $.

Keywords: coloring; complete bipartite graph; eigenvalues; interlacing

Posted by mdevos
updated February 26th, 2010
1 comment
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
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