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 chileqlceiltfrac12(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 leqfracDelta2+2?



This is known for Deltaleq4. In general for triangle-free graphs, chileqO(Delta/logDelta), 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 chileqfrac23Delta+2. He also proved that chileqfracDelta2+2 for graphs of sufficiently large girth depending on Delta. Can anyone prove it for girth geq5? 4?



This would at least provide some hope for proving Reed's Conjecture for triangle-free graphs.




Does every triangle-free graph with Deltaleq6 have chileq5? What about every graph with girth at least five?


No comments:

Post a Comment