@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 = "Funding Information: \ast Received by the editors August 28, 2018; accepted for publication (in revised form) September 19, 2019; published electronically February 19, 2020. https://doi.org/10.1137/18M1210290 Funding: This material is based upon work supported in part by the U.S. Army Research Laboratory under grant W911NF-16-1-0404. The first author was partially supported by NSF grant DMS-1550991 and U.S. Army Research Office grant W911NF-16-1-0404. The second author was supported by a Postdoctoral Fellowship of the Research Foundation Flanders (FWO). \dagger Mathematics Department, Princeton University, Princeton, NJ 08544 (mchudnov@math. princeton.edu). \ddagger Department of Applied Mathematics, Computer Science and Statistics, Ghent University, 9000 Ghent, Belgium, and University of Mons, Mons, Belgium (jan.goedgebeur@ugent.be). \S Lehrstuhl fu\{"}r Mathematik der Informationsverarbeitung, RWTH Aachen University, 52062 Aachen, Germany (schaudto@uni-koeln.de). \P Lehman College and the Graduate Center, City University of New York, New York, NY 10017 (mingxian.zhong@lehman.cuny.edu). Funding Information: This material is based upon work supported in part by the U.S. Army Research Laboratory under grant W911NF-16-1-0404. The first author was partially supported by NSF grant DMS-1550991 and U.S. Army Research Office grant W911NF-16-1-0404. The second author was supported by a Postdoctoral Fellowship of the Research Foundation Flanders (FWO). 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",
}