Friday, 11 May 2007

Does every triangle-free graph with maximum degree at most 6 have a 5-colouring?

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