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

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
Graph Theory » Infinite Graphs

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