Updating the complexity status of coloring graphs without a fixed induced linear forest
From MaRDI portal
Publication:764301
DOI10.1016/J.TCS.2011.10.005zbMATH Open1234.68129OpenAlexW2138290101MaRDI QIDQ764301FDOQ764301
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
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
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coloring of graphs and hypergraphs (05C15)
Cites Work
- Graph theory
- Title not available (Why is that?)
- The complexity of colouring problems on dense graphs
- The ellipsoid method and its consequences in combinatorial optimization
- 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
- Three complexity results on coloring \(P _{k }\)-free graphs
- A New Algorithm for Generating All the Maximal Independent Sets
- Title not available (Why is that?)
- The complexity of satisfiability problems
- Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
- Graph colorings with local constraints -- a survey
- The complexity of coloring graphs without long induced paths
- Vertex colouring and forbidden subgraphs -- a survey
- Coloring edges and vertices of graphs without short or long cycles
- On the complexity of 4-coloring graphs without long induced paths
- A certifying algorithm for 3-colorability of \(P _{5}\)-free graphs
- On graphs with polynomially solvable maximum-weight clique problem
- Determining the chromatic number of triangle-free \(2P_3\)-free graphs in polynomial time
- The 3-Colorability Problem on Graphs with Maximum Degree Four
- Title not available (Why is that?)
- Colouring vertices of triangle-free graphs
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
- Coloring graphs without short cycles and long induced paths
- Closing complexity gaps for coloring problems on \(H\)-free graphs
- The vertex colourability problem for \(\{\text{claw}, \text{butterfly}\}\)-free graphs is polynomial-time solvable
- 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
- Three complexity results on coloring \(P _{k }\)-free graphs
- 4-coloring \(H\)-free graphs when \(H\) is small
- 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
- On the complexity of the vertex 3-coloring problem for the hereditary graph classes with forbidden subgraphs of small size
- Critical hereditary graph classes: a survey
- A complexity dichotomy and a new boundary class for the dominating set problem
- Colouring (P_r+P_s)-Free Graphs
- The complexity of the 3-colorability problem in the absence of a pair of small forbidden induced subgraphs
- Coloring graphs characterized by a forbidden subgraph
- 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_3\)-free graphs in polynomial time
- Three complexity results on coloring \(P_k\)-free graphs
- A complete complexity dichotomy of the edge-coloring problem for all sets of 8-edge forbidden subgraphs
- 4-coloring \(H\)-free graphs when \(H\) is small
- Complexity dichotomy for list-5-coloring with a forbidden induced subgraph
- Title not available (Why is that?)
- 4‐Coloring P 6 ‐Free Graphs with No Induced 5‐Cycles
- 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)
