K4-free graphs with no odd holes

Maria Chudnovsky; Neil Robertson; Paul Seymour; Robin Thomas

doi:10.1016/j.jctb.2009.10.001

K₄-free graphs with no odd holes

Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas

Mathematics

Research output: Contribution to journal › Article › peer-review

29 Scopus citations

Abstract

All K₄-free graphs with no odd hole and no odd antihole are three-colourable, but what about K₄-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.

Original language	English (US)
Pages (from-to)	313-331
Number of pages	19
Journal	Journal of Combinatorial Theory. Series B
Volume	100
Issue number	3
DOIs	https://doi.org/10.1016/j.jctb.2009.10.001
State	Published - May 2010

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Keywords

Odd hole
Perfect graph

Access to Document

10.1016/j.jctb.2009.10.001

Cite this

@article{1c1c6609204449dd9151c2bed3ee4465,

title = "K4-free graphs with no odd holes",

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.",

keywords = "Odd hole, Perfect graph",

author = "Maria Chudnovsky and Neil Robertson and Paul Seymour and Robin Thomas",

note = "Funding Information: E-mail address: [email protected] (P. Seymour). 1 This research was conducted while the author served as a Clay Mathematics Institute Research Fellow. 2 Supported by NSF grant DMS-0071096. 3 Supported by ONR grants N00014-97-1-0512 and N00014-01-1-0608, and NSF grant DMS-0070912. 4 Supported by NSF grant DMS-9623031 and NSA grant MDA904-98-1-0517.",

year = "2010",

month = may,

doi = "10.1016/j.jctb.2009.10.001",

language = "English (US)",

volume = "100",

pages = "313--331",

journal = "Journal of Combinatorial Theory. Series B",

issn = "0095-8956",

publisher = "Academic Press Inc.",

number = "3",

}

TY - JOUR

T1 - K4-free graphs with no odd holes

AU - Chudnovsky, Maria

AU - Robertson, Neil

AU - Seymour, Paul

AU - Thomas, Robin

N1 - Funding Information: E-mail address: [email protected] (P. Seymour). 1 This research was conducted while the author served as a Clay Mathematics Institute Research Fellow. 2 Supported by NSF grant DMS-0071096. 3 Supported by ONR grants N00014-97-1-0512 and N00014-01-1-0608, and NSF grant DMS-0070912. 4 Supported by NSF grant DMS-9623031 and NSA grant MDA904-98-1-0517.

PY - 2010/5

Y1 - 2010/5

N2 - 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.

AB - 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.

KW - Odd hole

KW - Perfect graph

UR - https://www.scopus.com/pages/publications/77249170727

UR - https://www.scopus.com/inward/citedby.url?scp=77249170727&partnerID=8YFLogxK

U2 - 10.1016/j.jctb.2009.10.001

DO - 10.1016/j.jctb.2009.10.001

M3 - Article

AN - SCOPUS:77249170727

SN - 0095-8956

VL - 100

SP - 313

EP - 331

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

IS - 3

ER -