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

DOI10.1137/18M1210290zbMATH Open1433.05115arXiv1703.05684OpenAlexW3008343249MaRDI QIDQ5216779FDOQ5216779

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)

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.

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

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

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)

Cites Work

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

Cited In (8)

• \(k\)-critical graphs in \(P_5\)-free graphs
• Better 3-coloring algorithms: excluding a triangle and a seven vertex path
• Dichotomizing \(k\)-vertex-critical \(H\)-free graphs for \(H\) of order four
• 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

Uses Software

• House of Graphs
• CriticalPfreeGraphs

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)