Determining the chromatic number of triangle-free 2P₃-free graphs in polynomial time
DOI10.1016/J.TCS.2011.12.076zbMATH Open1241.05030OpenAlexW1982039109MaRDI QIDQ417995FDOQ417995
Authors: Petr A. Golovach, Daniël Paulusma, Jian Song, Hajo Broersma 
Publication date: 14 May 2012
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2011.12.076
Recommendations
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coloring of graphs and hypergraphs (05C15)
Cites Work
- The complexity of colouring problems on dense graphs
- On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
- 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
- Linear time solvable optimization problems on graphs of bounded clique-width
- 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?)
- Updating the complexity status of coloring graphs without a fixed induced linear forest
- 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
- Title not available (Why is that?)
- 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
- THE CLIQUE-WIDTH OF BIPARTITE GRAPHS IN MONOGENIC CLASSES
- Title not available (Why is that?)
- Triangle-free graphs and forbidden subgraphs
- Colouring vertices of triangle-free graphs
Cited In (26)
- Colouring of graphs with Ramsey-type forbidden subgraphs
- On the parameterized complexity of coloring graphs in the absence of a linear forest
- Clique-Width of Graph Classes Defined by Two Forbidden Induced Subgraphs
- Coloring graphs without short cycles and long induced paths
- Vertex coloring of graphs with few obstructions
- Coloring graphs without short cycles and long induced paths
- On the power of threshold-based algorithms for detecting cycles in the CONGEST model
- Maximum regular induced subgraphs in \(2P_3\)-free graphs
- Updating the complexity status of coloring graphs without a fixed induced linear forest
- Colouring square-free graphs without long induced paths.
- 4-coloring \(H\)-free graphs when \(H\) is small
- Sparse regular induced subgraphs in \(2P_3\)-free graphs
- List coloring in the absence of a linear forest
- Colouring square-free graphs without long induced paths
- List coloring in the absence of a linear forest
- Colouring diamond-free graphs
- A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs
- Colouring vertices of triangle-free graphs
- List coloring in the absence of two subgraphs
- Triangle-free \(2P_3\)-free graphs are 4-colorable
- 4-coloring \(H\)-free graphs when \(H\) is small
- A class of three-colorable triangle-free graphs
- On coloring graphs without induced forests
- Polynomial cases for the vertex coloring problem
- On colouring \((2P_2,H)\)-free and \((P_5,H)\)-free graphs
- On the power of threshold-based algorithms for detecting cycles in the \textsc{CONGEST} model
This page was built for publication: Determining the chromatic number of triangle-free \(2P_3\)-free graphs in polynomial time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q417995)
