42
$\begingroup$

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?

$\endgroup$
  • 4
    $\begingroup$ 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? $\endgroup$ – Joseph O'Rourke Sep 6 '10 at 20:41
  • 7
    $\begingroup$ 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 $\endgroup$ – Andrew D. King Sep 7 '10 at 16:30
  • 2
    $\begingroup$ 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$. $\endgroup$ – Joseph O'Rourke Sep 8 '10 at 16:25

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.