Obstructions for Three-Coloring and List Three-Coloring $H$-Free Graphs
From MaRDI portal
Publication:5216779
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
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
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