53
$\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?

Improve this question
$\endgroup$
3
  • 5
    $\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
    Commented Sep 6, 2010 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
    Commented Sep 7, 2010 at 16:30
  • 3
    $\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
    Commented Sep 8, 2010 at 16:25

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .