Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4657209 | Journal of Combinatorial Theory, Series B | 2010 | 19 Pages |
Abstract
All K4-free graphs with no odd hole and no odd antihole are three-colourable, but what about K4-free graphs with no odd hole? They are not necessarily three-colourable, but we prove a conjecture of Ding that they are all four-colourable. This is a consequence of a decomposition theorem for such graphs; we prove that every such graph either has no odd antihole, or belongs to one of two explicitly-constructed classes, or admits a decomposition.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics