Obstructions for three-coloring graphs without induced paths on six vertices

Maria Chudnovsky; Jan Goedgebeur; Oliver Schaudt; Mingxian Zhong

doi:10.1016/j.jctb.2019.04.006

Obstructions for three-coloring graphs without induced paths on six vertices

Maria Chudnovsky, Jan Goedgebeur, Oliver Schaudt, Mingxian Zhong

Mathematics

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

13 Scopus citations

Abstract

We prove that there are 24 4-critical P₆-free graphs, and give the complete list. We remark that, if H is connected and not a subgraph of P₆, there are infinitely many 4-critical H-free graphs. Our result answers questions of Golovach et al. and Seymour.

Original language	English (US)
Pages (from-to)	45-83
Number of pages	39
Journal	Journal of Combinatorial Theory. Series B
Volume	140
DOIs	https://doi.org/10.1016/j.jctb.2019.04.006
State	Published - Jan 2020

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Keywords

Critical graph
Forbidden induced paths
Graph coloring

Access to Document

10.1016/j.jctb.2019.04.006

Cite this

@article{b6417b9a2dc7417499614ef1574a8875,

title = "Obstructions for three-coloring graphs without induced paths on six vertices",

abstract = "We prove that there are 24 4-critical P6-free graphs, and give the complete list. We remark that, if H is connected and not a subgraph of P6, there are infinitely many 4-critical H-free graphs. Our result answers questions of Golovach et al. and Seymour.",

keywords = "Critical graph, Forbidden induced paths, Graph coloring",

author = "Maria Chudnovsky and Jan Goedgebeur and Oliver Schaudt and Mingxian Zhong",

note = "Publisher Copyright: {\textcopyright} 2019",

year = "2020",

month = jan,

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

language = "English (US)",

volume = "140",

pages = "45--83",

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

issn = "0095-8956",

publisher = "Academic Press Inc.",

}

TY - JOUR

T1 - Obstructions for three-coloring graphs without induced paths on six vertices

AU - Chudnovsky, Maria

AU - Goedgebeur, Jan

AU - Schaudt, Oliver

AU - Zhong, Mingxian

PY - 2020/1

Y1 - 2020/1

N2 - We prove that there are 24 4-critical P6-free graphs, and give the complete list. We remark that, if H is connected and not a subgraph of P6, there are infinitely many 4-critical H-free graphs. Our result answers questions of Golovach et al. and Seymour.

AB - We prove that there are 24 4-critical P6-free graphs, and give the complete list. We remark that, if H is connected and not a subgraph of P6, there are infinitely many 4-critical H-free graphs. Our result answers questions of Golovach et al. and Seymour.

KW - Critical graph

KW - Forbidden induced paths

KW - Graph coloring

UR - http://www.scopus.com/inward/record.url?scp=85067351414&partnerID=8YFLogxK

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

U2 - 10.1016/j.jctb.2019.04.006

DO - 10.1016/j.jctb.2019.04.006

M3 - Article

AN - SCOPUS:85067351414

SN - 0095-8956

VL - 140

SP - 45

EP - 83

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

ER -

Obstructions for three-coloring graphs without induced paths on six vertices

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this