Title of article
k4-free graphs with no odd holes
Author/Authors
Chudnovsky، Maria نويسنده , , Robertson، Neil نويسنده , , Seymour، Paul نويسنده , , Thomas، Robin نويسنده ,
Issue Information
روزنامه با شماره پیاپی سال 2010
Pages
19
From page
313
To page
331
Abstract
All K 4 -free graphs with no odd hole and no odd antihole are three-colourable, but what about K 4 -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.
Keywords
Perfect graph , Odd hole
Journal title
Journal of Combinatorial Theory Series B
Serial Year
2010
Journal title
Journal of Combinatorial Theory Series B
Record number
1528042
Link To Document