Obstructions for three-coloring and list three-coloring H-free graphs

DOI10.1137/18M1210290MaRDI QIDQ5216779zbMATH OpenOpenAlexFDO

Authors Maria Chudnovsky, Jan Goedgebeur, Oliver Schaudt, 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

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

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-three-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.

Recommendations

• Three-coloring and list three-coloring of graphs without induced paths on seven vertices
• Obstructions for three-coloring graphs without induced paths on six vertices
• Closing complexity gaps for coloring problems on \(H\)-free graphs
• Closing complexity gaps for coloring problems on \(H\)-free graphs
• 4-coloring \(H\)-free graphs when \(H\) is small

Cites work

• scientific article; zbMATH DE number 2044943 (Why is no real title available?)
• 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
• A Ramsey-type theorem for traceable graphs
• A certifying algorithm for 3-colorability of \(P _{5}\)-free graphs
• A new characterization of P_k-free graphs
• A survey on the computational complexity of coloring graphs with forbidden subgraphs
• Coloring edges and vertices of graphs without short or long cycles
• Complexity of coloring graphs without paths and cycles
• Constructions of k-critical P₅-free graphs
• Data reduction for graph coloring problems
• Exhaustive generation of \(k\)-critical \(\mathcal{H}\)-free graphs
• Explicit construction of graphs with an arbitrary large girth and of large size
• Graph Theory and Probability
• House of Graphs: a database of interesting graphs
• NP completeness of finding the chromatic index of regular graphs
• Obstructions for three-coloring graphs with one forbidden induced subgraph
• Obstructions for three-coloring graphs without induced paths on six vertices
• On 3-colorable \(P_5\)-free graphs
• On a property of the class of n-colorable graphs
• The NP-Completeness of Edge-Coloring
• Three-coloring and list three-coloring of graphs without induced paths on seven vertices

Cited in

(8)

• Better 3-coloring algorithms: excluding a triangle and a seven vertex path
• Dichotomizing \(k\)-vertex-critical \(H\)-free graphs for \(H\) of order four
• \(k\)-critical graphs in \(P_5\)-free graphs
• 3-dynamic coloring and list 3-dynamic coloring of \(K_{1, 3}\)-free graphs
• Three-coloring and list three-coloring of graphs without induced paths on seven vertices
• Forbidden triples generating a finite set of graphs with minimum degree three
• \(k\)-critical graphs in \(P_5\)-free graphs
• Vertex-critical \(( P_3 + \ell P_1 )\)-free and vertex-critical (gem, co-gem)-free graphs

Describes a project that uses

Uses Software

• CriticalPfreeGraphs
• House of Graphs

This page was built for publication: Obstructions for three-coloring and list three-coloring \(H\)-free graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5216779)