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

DOI10.1016/J.TCS.2011.10.005MaRDI QIDQ764301zbMATH OpenOpenAlexFDO

Authors Petr A. Golovach, Daniël Paulusma, Jian Song, Hajo 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 coloringforbidden induced subgraphlinear forest

Mathematics Subject Classification ID

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

Recommendations

• On the parameterized complexity of coloring graphs in the absence of a linear forest
• On coloring graphs without induced forests
• The complexity of coloring graphs without long induced paths
• scientific article; zbMATH DE number 2044943
• The complexity of the empire colouring problem for linear forests
• Narrowing Down the Gap on the Complexity of Coloring P k -Free Graphs
• Complexity of coloring graphs without paths and cycles
• Complexity of coloring graphs without paths and cycles

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2044943 (Why is no real title available?)
• scientific article; zbMATH DE number 772747 (Why is no real title available?)
• 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
• A New Algorithm for Generating All the Maximal Independent Sets
• A certifying algorithm for 3-colorability of \(P _{5}\)-free graphs
• Coloring edges and vertices of graphs without short or long cycles
• Colouring vertices of triangle-free graphs
• Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
• Determining the chromatic number of triangle-free 2P₃-free graphs in polynomial time
• Graph colorings with local constraints -- a survey
• Graph theory
• On graphs with polynomially solvable maximum-weight clique problem
• On the complexity of 4-coloring graphs without long induced paths
• The 3-Colorability Problem on Graphs with Maximum Degree Four
• The complexity of coloring graphs without long induced paths
• The complexity of colouring problems on dense graphs
• The complexity of satisfiability problems
• The ellipsoid method and its consequences in combinatorial optimization
• Three complexity results on coloring \(P _{k }\)-free graphs
• Vertex colouring and forbidden subgraphs -- a survey

Cited in

(44)

• Colouring of graphs with Ramsey-type forbidden subgraphs
• On the parameterized complexity of coloring graphs in the absence of a linear forest
• A dichotomy for the dominating set problem for classes defined by small forbidden induced subgraphs
• The vertex colourability problem for \(\{\text{claw}, \text{butterfly}\}\)-free graphs is polynomial-time solvable
• Closing complexity gaps for coloring problems on \(H\)-free graphs
• Coloring graphs without short cycles and long induced paths
• 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
• 4-coloring \((P_6, \text{bull})\)-free graphs
• On the chromatic number of (\(P_6\), diamond)-free graphs
• An intractability result for the vertex 3-colourability problem
• Colouring \((P_r + P_s)\)-free graphs
• 4-coloring \(H\)-free graphs when \(H\) is small
• Three complexity results on coloring \(P _{k }\)-free graphs
• List coloring in the absence of a linear forest
• Complete complexity dichotomy for 7-edge forbidden subgraphs in the edge coloring problem
• List coloring in the absence of a linear forest
• The complexity of the vertex 3-colorability problem for some hereditary classes defined by 5-vertex forbidden induced subgraphs
• Coloring (\(P_5\), kite)-free graphs with small cliques
• On the price of independence for vertex cover, feedback vertex set and odd cycle transversal
• Critical hereditary graph classes: a survey
• A complexity dichotomy and a new boundary class for the dominating set problem
• On the complexity of the vertex 3-coloring problem for the hereditary graph classes with forbidden subgraphs of small size
• Coloring graphs characterized by a forbidden subgraph
• The complexity of the 3-colorability problem in the absence of a pair of small forbidden induced subgraphs
• Colouring (P_r+P_s)-Free Graphs
• Coloring of pseudocubic graphs in three colors
• List coloring in the absence of two subgraphs
• List 3-coloring graphs with no induced \(P_6 + rP_3\)
• Complexity classification of the edge coloring problem for a family of graph classes
• Complexity of coloring graphs without paths and cycles
• Determining the chromatic number of triangle-free 2P₃-free graphs in polynomial time
• Three complexity results on coloring \(P_k\)-free graphs
• 4-coloring \(H\)-free graphs when \(H\) is small
• A complete complexity dichotomy of the edge-coloring problem for all sets of 8-edge forbidden subgraphs
• Complexity dichotomy for list-5-coloring with a forbidden induced subgraph
• 4‐Coloring P ₆ ‐Free Graphs with No Induced 5‐Cycles
• scientific article; zbMATH DE number 7651161 (Why is no real title available?)
• Clique-width of graph classes defined by two forbidden induced subgraphs
• Improved complexity results on \(k\)-coloring \(P_t\)-free graphs
• Two complexity results for the vertex coloring problem
• On coloring graphs without induced forests
• 3-colouring \(P_t\)-free graphs without short odd cycles

This page was built for publication: Updating the complexity status of coloring graphs without a fixed induced linear forest

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