Open Problem Garden - Reed's omega, delta, and chi conjecture - Comments

changed (re: Reed's omega, delta, and chi conjecture)

Robert Samal — Mon, 24 Sep 2007 20:34:30 +0200

Thanks for the comment. I changed the statement to the conjectured (slightly stronger) version with round-up.

The statement of the (re: Reed's omega, delta, and chi conjecture)

Anonymous — Tue, 18 Sep 2007 22:06:59 +0200

The statement of the conjecture is slightly incorrect. Instead of the +1 at the end, there should simply be a round-up. The conjecture is true for line graphs and quasi-line graphs, graphs with independence number 2, and any graph on I believe 12 vertices.

An outright proof of the result for triangle-free graphs would be very nice. Lovasz' result on splitting graphs is not quite enough in this case.

Reed's omega, delta, and chi conjecture

mdevos — Tue, 22 May 2007 21:07:47 +0200

Author(s): Reed

Subject: Graph Theory » Coloring » Vertex coloring

For a graph , we define to be the maximum degree, to be the size of the largest clique subgraph, and to be the chromatic number of .

Conjecture for every graph .