A very specific case of Reed's Conjecture
Reed's omegaomega,DeltaDelta, chichi conjecture proposes that every graph has chileqlceiltfrac12(Delta+1+omega)rceilchileqlceiltfrac12(Delta+1+omega)rceil. Here chichi is the chromatic number, DeltaDelta is the maximum degree, and omegaomega is the clique number.
When restricted to triangle-free graphs, the equivalent question is, Does every triangle-free graph have chromatic number leqfracDelta2+2leqfracDelta2+2?
This is known for Deltaleq4Deltaleq4. In general for triangle-free graphs, chileqO(Delta/logDelta)chileqO(Delta/logDelta), so the conjecture is also true for very large DeltaDelta.
How about Delta=5Delta=5? Delta=6Delta=6? Because of parity, Delta=6Delta=6 is the easier of these two cases (and actually easily implies the Delta=5Delta=5 case. Can anyone prove it?
Kostochka proved that every triangle-free graph has chileqfrac23Delta+2chileqfrac23Delta+2. He also proved that chileqfracDelta2+2chileqfracDelta2+2 for graphs of sufficiently large girth depending on DeltaDelta. Can anyone prove it for girth geq5geq5? 44?
This would at least provide some hope for proving Reed's Conjecture for triangle-free graphs.
Does every triangle-free graph with Deltaleq6Deltaleq6 have chileq5chileq5? What about every graph with girth at least five?
No comments:
Post a Comment