Obstructions for Three-Coloring and List Three-Coloring $H$-Free Graphs
SIAM Journal on Discrete Mathematics · 2020-01 · 34 (1) · 431-469
DOI: 10.1137/18m1210290 ↗Kurz gefasst
Fachartikel in der Zeitschrift SIAM Journal on Discrete Mathematics, online erschienen am 19.02.2020. Verfasst von Maria Chudnovsky und 3 weiteren Autor:innen. Die Arbeit wurde bisher 9-mal zitiert (Crossref) und nennt 24 Literaturangaben. Gefördert von: Army Research Laboratory, Army Research Office, Fonds Wetenschappelijk Onderzoek.
Abstract (Originalsprache)
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.
Förderung
- Army Research Laboratory
- Army Research Office
- Fonds Wetenschappelijk Onderzoek
- National Science Foundation
Zitieren
APA
Chudnovsky, M., Goedgebeur, J., Schaudt, O., & Zhong, M. (2020). Obstructions for Three-Coloring and List Three-Coloring $H$-Free Graphs. SIAM Journal on Discrete Mathematics, 34(1), 431-469. https://doi.org/10.1137/18m1210290
Vancouver
Chudnovsky M, Goedgebeur J, Schaudt O, Zhong M. Obstructions for Three-Coloring and List Three-Coloring $H$-Free Graphs. SIAM Journal on Discrete Mathematics. 2020;34(1):431-469. doi:10.1137/18m1210290
BibTeX
@article{Chudnovsky2020,
author = {Chudnovsky, Maria and Goedgebeur, Jan and Schaudt, Oliver and Zhong, Mingxian},
title = {Obstructions for Three-Coloring and List Three-Coloring $H$-Free Graphs},
journal = {SIAM Journal on Discrete Mathematics},
year = {2020},
volume = {34},
number = {1},
pages = {431--469},
doi = {10.1137/18m1210290}
}
EUVIMED