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

DOI10.1137/18M1210290zbMath1433.05115arXiv1703.05684MaRDI QIDQ5216779

Maria Chudnovsky, Oliver Schaudt, Jan Goedgebeur, Mingxian Zhong

Publication date: 20 February 2020

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1703.05684

zbMATH Keywords

graph coloring; induced subgraph; critical graph

Mathematics Subject Classification ID

05C15: Coloring of graphs and hypergraphs

05C85: Graph algorithms (graph-theoretic aspects)

05C60: Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)

Uses Software

• House of Graphs
• CriticalPfreeGraphs