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

Grunbaum's Conjecture ★★★

Author(s): Grunbaum

Conjecture   If $ G $ is a simple loopless triangulation of an orientable surface, then the dual of $ G $ is 3-edge-colorable.

Keywords: coloring; surface

Linial-Berge path partition duality ★★★

Author(s): Berge; Linial

Conjecture   The minimum $ k $-norm of a path partition on a directed graph $ D $ is no more than the maximal size of an induced $ k $-colorable subgraph.

Keywords: coloring; directed path; partition

Syndicate content