4-coloring \(H\)-free graphs when \(H\) is small
From MaRDI portal
Publication:1759872
DOI10.1016/j.dam.2012.08.022zbMath1259.05061OpenAlexW1565326817MaRDI QIDQ1759872
Petr A. Golovach, Jian Song, Daniël Paulusma
Publication date: 22 November 2012
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2012.08.022
Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (20)
The vertex colourability problem for \(\{\text{claw}, \text{butterfly}\}\)-free graphs is polynomial-time solvable ⋮ An intractability result for the vertex 3-colourability problem ⋮ List coloring in the absence of two subgraphs ⋮ A complexity dichotomy and a new boundary class for the dominating set problem ⋮ Vertex coloring of graphs with few obstructions ⋮ Complexity classification of the edge coloring problem for a family of graph classes ⋮ The complexity of the vertex 3-colorability problem for some hereditary classes defined by 5-vertex forbidden induced subgraphs ⋮ Complete complexity dichotomy for $7$-edge forbidden subgraphs in the edge coloring problem ⋮ Colouring of graphs with Ramsey-type forbidden subgraphs ⋮ A complete classification of the complexity of the vertex 3-colourability problem for quadruples of induced 5-vertex prohibitions ⋮ Coloring graphs without short cycles and long induced paths ⋮ A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs ⋮ Coloring graphs characterized by a forbidden subgraph ⋮ Improved complexity results on \(k\)-coloring \(P_t\)-free graphs ⋮ Two complexity results for the vertex coloring problem ⋮ Critical hereditary graph classes: a survey ⋮ Coloring of pseudocubic graphs in three colors ⋮ On the Complexity of the Vertex 3-Coloring Problem for the Hereditary Graph Classes With Forbidden Subgraphs of Small Size ⋮ The complexity of the 3-colorability problem in the absence of a pair of small forbidden induced subgraphs ⋮ A dichotomy for the dominating set problem for classes defined by small forbidden induced subgraphs
This page was built for publication: 4-coloring \(H\)-free graphs when \(H\) is small
