most recent 30 from http://mathoverflow.net 2013-05-24T08:45:25Z http://mathoverflow.net/feeds/question/37923 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/37923/does-every-triangle-free-graph-with-maximum-degree-at-most-6-have-a-5-colouring Andrew D. King 2010-09-06T19:58:11Z 2010-09-06T20:38:14Z

<h2>A very specific case of Reed's Conjecture</h2> <p>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.</p> <p>When restricted to triangle-free graphs, the equivalent question is, Does every triangle-free graph have chromatic number $\leq \frac \Delta 2 +2$?</p> <p>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$.</p> <p>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?</p> <p>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$?</p> <p>This would at least provide some hope for proving Reed's Conjecture for triangle-free graphs.</p> <blockquote> <p>Does every triangle-free graph with $\Delta\leq 6$ have $\chi \leq 5$? What about every graph with girth at least five?</p> </blockquote>