Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

A very specific case of Reed's Conjecture

Reed's $\omega$,$\Delta$, $\chi$ conjecture proposes that every graph has $\chi \leq \lceil \tfrac 12(\Delta+1+\omega)\rceil$. Here $\chi$ is the chromatic number, $\Delta$ is the maximum degree, and $\omega$ is the clique number.

When restricted to triangle-free graphs, the equivalent question is, Does every triangle-free graph have chromatic number $\leq \frac \Delta 2 +2$?

This is known for $\Delta\leq 4$. In general for triangle-free graphs, $\chi \leq O(\Delta/\log \Delta)$, so the conjecture is also true for very large $\Delta$.

How about $\Delta=5$? $\Delta=6$? Because of parity, $\Delta=6$ is the easier of these two cases (and actually easily implies the $\Delta=5$ case. Can anyone prove it?

Kostochka proved that every triangle-free graph has $\chi \leq \frac 2 3 \Delta +2$. He also proved that $\chi\leq \frac \Delta 2 +2$ for graphs of sufficiently large girth depending on $\Delta$. Can anyone prove it for girth $\geq 5$? $4$?

This would at least provide some hope for proving Reed's Conjecture for triangle-free graphs.

Does every triangle-free graph with $\Delta\leq 6$ have $\chi \leq 5$? What about every graph with girth at least five?

share|improve this question
This is not addressing your question, but I wonder if it is known whether Reed's conjecture holds when $\chi$ is replaced by $\chi_f$, the fractional chromatic number? –  Joseph O'Rourke Sep 6 '10 at 20:41
Good question; it is known to hold, without the round-up. Reed never published the result in a paper but it's in Graph Colouring and the Probabilistic Method (with Molloy), in the chapter on hard-core distributions (Chapter 23 I think). (It wouldn't let me comment twice in a row, so I deleted the old comment to add: ) A proof of a stronger result, noted by McDiarmid, appears in Section 2.2 of my thesis, which is here: columbia.edu/~ak3074/papers/phdthesis.pdf –  Andrew D. King Sep 7 '10 at 16:30
Another possible tangential attack is to establish the conjecture for the "warmth" $w$ of the graph, because Brightwell and Winkler proved that $w \le \chi$. –  Joseph O'Rourke Sep 8 '10 at 16:25
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.