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 $Deltaleq 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 $chileq 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 $Deltaleq 6$ have $chi leq 5$? What about every graph with girth at least five?
No comments:
Post a Comment