Reed's omega, delta, and chi conjecture

Importance: High ✭✭✭
Author(s): Reed, Bruce A.
Keywords: coloring
Recomm. for undergrads: no
Posted by: mdevos
on: May 22nd, 2007

For a graph $G$, we define $\Delta(G)$ to be the maximum degree, $\omega(G)$ to be the size of the largest \Def[clique]{clique (graph theory)} subgraph, and $\chi(G)$ to be the chromatic number of $G$.

\begin{conjecture} $\chi(G) \le \ceil{\frac{1}{2}(\Delta(G)+1) + \frac{1}{2}\omega(G)}$ for every graph $G$. \end{conjecture}

Perhaps the two most trivial bounds on $\chi(G)$ are $\chi(G) \ge \omega(G)$ and $\chi(G) \le \Delta(G) + 1$. The above conjecture roughly asserts that the (rounded-up) average of $\Delta(G)+1$ and $\omega(G)$ should again be an upper bound on $\chi(G)$.

The conjecture is easy to verify when $\omega(G)$ is very large. It is trivial when $\omega(G) \ge \Delta(G)$, and it follows from Brook's theorem if $\omega(G) = \Delta(G)-1$. On the other hand, if $\omega(G) = 2$, so $G$ is triangle free, then the conjecture is also true for $\Delta$ sufficiently large. Indeed, Johannsen proved the much stronger fact that there exists a fixed constant $c$ so that $\chi(G) \le \frac{c \Delta(G)}{\log \Delta(G)}$ for every triangle free graph $G$.

Reed showed that the conjecture holds when $\Delta(G) = |V(G)| - 1$ by way of matching theory. More interestingly, he proved (using probabilistc methods) that the conjecture is true provided that $\Delta$ is sufficiently large, and $\omega$ is sufficiently close to $\Delta$. More precisely, he proves the following:

\begin{theorem} There exists a fixed constant $\Delta_0$ such that for every $\Delta \ge \Delta_0$, if $G$ is a graph of maximum degree $\Delta$ with no clique of size $>k$ for some $k \ge (1 - \frac{1}{70000000}) \Delta$ then $\chi(G) \le \frac{\Delta + 1 + k}{2}$. \end{theorem}

It is known that the conjecture is true fractionally (that is with $\chi(G)$ replaced by $\chi_f(G)$, the \Def{fractional chromatic number} of~$G$).


*[R] B. Reed, $\omega, \Delta$, and $\chi$, J. Graph Theory 27 (1998) 177-212.

* indicates original appearance(s) of problem.

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.


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

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.