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

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

Jan Goedgebeur, Oliver Schaudt, Maria Chudnovsky, 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 coloringinduced subgraphcritical graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (5)

Dichotomizing \(k\)-vertex-critical \(H\)-free graphs for \(H\) of order four ⋮ Vertex-critical \(( P_3 + \ell P_1 )\)-free and vertex-critical (gem, co-gem)-free graphs ⋮ Better 3-coloring algorithms: excluding a triangle and a seven vertex path ⋮ \(k\)-critical graphs in \(P_5\)-free graphs ⋮ \(k\)-critical graphs in \(P_5\)-free graphs

Uses Software

• House of Graphs
• CriticalPfreeGraphs

Cites Work

• Unnamed Item
• Unnamed Item
• A new characterization of \(P_k\)-free graphs
• Complexity of coloring graphs without paths and cycles
• Data reduction for graph coloring problems
• A Ramsey-type theorem for traceable graphs
• 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
• House of Graphs: a database of interesting graphs
• Three-coloring and list three-coloring of graphs without induced paths on seven vertices
• Explicit construction of graphs with an arbitrary large girth and of large size
• Constructions of \(k\)-critical \(P_5\)-free graphs
• Obstructions for three-coloring graphs without induced paths on six vertices
• On a property of the class of n-colorable graphs
• A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs
• Graph Theory and Probability
• A Certifying Algorithm for 3-Colorability of P 5-Free Graphs
• The NP-Completeness of Edge-Coloring
• Obstructions for three-coloring graphs with one forbidden induced subgraph
• Exhaustive generation of k‐critical ‐free graphs
• NP completeness of finding the chromatic index of regular graphs
• On $3$-Colorable $P_5$-Free Graphs

This page was built for publication: Obstructions for Three-Coloring and List Three-Coloring $H$-Free Graphs