A very specific case of Reed's Conjecture
Reed's ,, conjecture proposes that every graph has . Here is the chromatic number, is the maximum degree, and is the clique number.
When restricted to triangle-free graphs, the equivalent question is, Does every triangle-free graph have chromatic number ?
This is known for . In general for triangle-free graphs, , so the conjecture is also true for very large .
How about ? ? Because of parity, is the easier of these two cases (and actually easily implies the case. Can anyone prove it?
Kostochka proved that every triangle-free graph has . He also proved that for graphs of sufficiently large girth depending on . Can anyone prove it for girth ? ?
This would at least provide some hope for proving Reed's Conjecture for triangle-free graphs.
Does every triangle-free graph with have ? What about every graph with girth at least five?
No comments:
Post a Comment