Reed's omega, delta, and chi conjecture
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 .
Perhaps the two most trivial bounds on are and . The above conjecture roughly asserts that the (rounded-up) average of and should again be an upper bound on .
The conjecture is easy to verify when is very large. It is trivial when , and it follows from Brook's theorem if . On the other hand, if , so is triangle free, then the conjecture is also true for sufficiently large. Indeed, Johannsen proved the much stronger fact that there exists a fixed constant so that for every triangle free graph .
Reed showed that the conjecture holds when by way of matching theory. More interestingly, he proved (using probabilistc methods) that the conjecture is true provided that is sufficiently large, and is sufficiently close to . More precisely, he proves the following:
It is known that the conjecture is true fractionally (that is with replaced by , the fractional chromatic number of~).
Bibliography
*[R] B. Reed, , and , J. Graph Theory 27 (1998) 177-212.
* indicates original appearance(s) of problem.
changed
Thanks for the comment. I changed the statement to the conjectured (slightly stronger) version with round-up.
The statement of the
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.