Obstructions for three-coloring and list three-coloring h -free graphs

Maria Chudnovsky; Jan Goedgebeur; Oliver Schaudt; Mingxian Zhong

doi:10.1137/18M1210290

Obstructions for three-coloring and list three-coloring h -free graphs

Maria Chudnovsky, Jan Goedgebeur, Oliver Schaudt, Mingxian Zhong

Mathematics

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

7 Scopus citations

Abstract

A graph is H-free if it has no induced subgraph isomorphic to H. We characterize all graphs H for which there are only finitely many minimal non-3-colorable H-free graphs. Such a characterization was previously known only in the case when H is connected. This solves a problem posed by Golovach et al. As a second result, we characterize all graphs H for which there are only finitely many H-free minimal obstructions for list 3-colorability.

Original language	English (US)
Pages (from-to)	431-469
Number of pages	39
Journal	SIAM Journal on Discrete Mathematics
Volume	34
Issue number	1
DOIs	https://doi.org/10.1137/18M1210290
State	Published - 2020

All Science Journal Classification (ASJC) codes

General Mathematics

Keywords

Critical graph
Graph coloring
Induced subgraph

Access to Document

10.1137/18M1210290

Cite this

@article{a1a2355fd5a3495d8f5ebfc273c24d71,

title = "Obstructions for three-coloring and list three-coloring h -free graphs",

abstract = "A graph is H-free if it has no induced subgraph isomorphic to H. We characterize all graphs H for which there are only finitely many minimal non-3-colorable H-free graphs. Such a characterization was previously known only in the case when H is connected. This solves a problem posed by Golovach et al. As a second result, we characterize all graphs H for which there are only finitely many H-free minimal obstructions for list 3-colorability.",

keywords = "Critical graph, Graph coloring, Induced subgraph",

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

note = "Publisher Copyright: {\textcopyright} 2020, Society for Industrial and Applied Mathematics.",

year = "2020",

doi = "10.1137/18M1210290",

language = "English (US)",

volume = "34",

pages = "431--469",

journal = "SIAM Journal on Discrete Mathematics",

issn = "0895-4801",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "1",

}

TY - JOUR

T1 - Obstructions for three-coloring and list three-coloring h -free graphs

AU - Chudnovsky, Maria

AU - Goedgebeur, Jan

AU - Schaudt, Oliver

AU - Zhong, Mingxian

PY - 2020

Y1 - 2020

N2 - A graph is H-free if it has no induced subgraph isomorphic to H. We characterize all graphs H for which there are only finitely many minimal non-3-colorable H-free graphs. Such a characterization was previously known only in the case when H is connected. This solves a problem posed by Golovach et al. As a second result, we characterize all graphs H for which there are only finitely many H-free minimal obstructions for list 3-colorability.

AB - A graph is H-free if it has no induced subgraph isomorphic to H. We characterize all graphs H for which there are only finitely many minimal non-3-colorable H-free graphs. Such a characterization was previously known only in the case when H is connected. This solves a problem posed by Golovach et al. As a second result, we characterize all graphs H for which there are only finitely many H-free minimal obstructions for list 3-colorability.

KW - Critical graph

KW - Graph coloring

KW - Induced subgraph

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

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

U2 - 10.1137/18M1210290

DO - 10.1137/18M1210290

M3 - Article

AN - SCOPUS:85091062403

SN - 0895-4801

VL - 34

SP - 431

EP - 469

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

IS - 1

ER -

Obstructions for three-coloring and list three-coloring h -free graphs

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this