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 .

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:

**Theorem**There exists a fixed constant such that for every , if is a graph of maximum degree with no clique of size for some then .

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.