Obstructions for Three-Coloring and List Three-Coloring $H$-Free Graphs

SIAM Journal on Discrete Mathematics, vol. 34, pp. 431–469

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.

Authors 4

1. Maria Chudnovsky

   Princeton University

   Affiliation as printed

   Mathematics Department, Princeton University, Princeton, NJ 08544

2. Jan Goedgebeur Aachen \S Lehrstuhl f\" ur Mathematik der Informationsverarbeitung

   RWTH Aachen University · University of Mons · Ghent University · City University of New York · Lehman College

   Affiliation as printed

   University of Mons, Mons, Belgium

   \P Lehman College and the Graduate Center, City University of New York, New York, NY 10017

   \S Lehrstuhl f\" ur Mathematik der Informationsverarbeitung, RWTH Aachen University, 52062 Aachen, Germany

   \ddagger Department of Applied Mathematics, Computer Science and Statistics, Ghent University, 9000 Ghent, Belgium, and

3. Oliver Schaudt corresponding Aachen \S Lehrstuhl f\" ur Mathematik der Informationsverarbeitung

   RWTH Aachen University · University of Mons · Ghent University · City University of New York · Lehman College

   Affiliation as printed

   University of Mons, Mons, Belgium

   \P Lehman College and the Graduate Center, City University of New York, New York, NY 10017

   \S Lehrstuhl f\" ur Mathematik der Informationsverarbeitung, RWTH Aachen University, 52062 Aachen, Germany

   \ddagger Department of Applied Mathematics, Computer Science and Statistics, Ghent University, 9000 Ghent, Belgium, and

4. Mingxian Zhong