Prefer a chat interface with context about you and your work?
Obstructions for Three-Coloring and List Three-Coloring $H$-Free Graphs
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 …