Updating the complexity status of coloring graphs without a fixed induced linear forest

DOI10.1016/j.tcs.2011.10.005zbMath1234.68129OpenAlexW2138290101MaRDI QIDQ764301

Jian Song, Daniël Paulusma, Petr A. Golovach, Hajo J. Broersma

Publication date: 13 March 2012

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2011.10.005

zbMATH Keywords

graph coloring forbidden induced subgraph linear forest

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

The vertex colourability problem for $\{\text{claw}, \text{butterfly}\}$-free graphs is polynomial-time solvable ⋮ 4-Coloring H-Free Graphs When H Is Small ⋮ 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 ⋮ Complexity of coloring graphs without paths and cycles ⋮ 4-coloring $(P_6, \text{bull})$-free graphs ⋮ 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 $(P_r + P_s)$-free graphs ⋮ On the chromatic number of ($P_6$, diamond)-free graphs ⋮ Clique-Width of Graph Classes Defined by Two Forbidden Induced Subgraphs ⋮ Colouring of graphs with Ramsey-type forbidden subgraphs ⋮ Complexity Dichotomy for List-5-Coloring with a Forbidden Induced Subgraph ⋮ A complete classification of the complexity of the vertex 3-colourability problem for quadruples of induced 5-vertex prohibitions ⋮ Determining the chromatic number of triangle-free $2P_3$-free graphs in polynomial time ⋮ Unnamed Item ⋮ Coloring ($P_5$, kite)-free graphs with small cliques ⋮ On the price of independence for vertex cover, feedback vertex set and odd cycle transversal ⋮ 3-colouring $P_t$-free graphs without short odd cycles ⋮ Coloring graphs without short cycles and long induced paths ⋮ 4‐Coloring P ₆ ‐Free Graphs with No Induced 5‐Cycles ⋮ A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs ⋮ On the parameterized complexity of coloring graphs in the absence of a linear forest ⋮ List 3-coloring graphs with no induced $P_6 + rP_3$ ⋮ 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 ⋮ Closing complexity gaps for coloring problems on $H$-free graphs ⋮ List coloring in the absence of a linear forest ⋮ 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 ⋮ Coloring Graphs without Short Cycles and Long Induced Paths ⋮ Colouring (P_r+P_s)-Free Graphs ⋮ List Coloring in the Absence of a Linear Forest ⋮ 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

Cites Work