Determining the chromatic number of triangle-free \(2P_3\)-free graphs in polynomial time
From MaRDI portal
Publication:417995
DOI10.1016/j.tcs.2011.12.076zbMath1241.05030OpenAlexW1982039109MaRDI QIDQ417995
Daniël Paulusma, Jian Song, Petr A. Golovach, Hajo J. 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
Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (21)
4-Coloring H-Free Graphs When H Is Small ⋮ List coloring in the absence of two subgraphs ⋮ Vertex coloring of graphs with few obstructions ⋮ Colouring diamond-free graphs ⋮ Colouring square-free graphs without long induced paths. ⋮ Clique-Width of Graph Classes Defined by Two Forbidden Induced Subgraphs ⋮ Colouring of graphs with Ramsey-type forbidden subgraphs ⋮ On the power of threshold-based algorithms for detecting cycles in the \textsc{CONGEST} model ⋮ On the power of threshold-based algorithms for detecting cycles in the CONGEST model ⋮ On colouring \((2P_2,H)\)-free and \((P_5,H)\)-free graphs ⋮ Coloring graphs without short cycles and long induced paths ⋮ 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 ⋮ Polynomial cases for the vertex coloring problem ⋮ Maximum regular induced subgraphs in \(2P_3\)-free graphs ⋮ List coloring in the absence of a linear forest ⋮ Sparse regular induced subgraphs in \(2P_3\)-free graphs ⋮ Coloring Graphs without Short Cycles and Long Induced Paths ⋮ Updating the complexity status of coloring graphs without a fixed induced linear forest ⋮ List Coloring in the Absence of a Linear Forest ⋮ Colouring square-free graphs without long induced paths
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Updating the complexity status of coloring graphs without a fixed induced linear forest
- Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
- 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.
- Triangle-free graphs and forbidden subgraphs
- Vertex colouring and forbidden subgraphs -- a survey
- Linear time solvable optimization problems on graphs of bounded clique-width
- On the complexity of 4-coloring graphs without long induced paths
- Colouring Vertices of Triangle-Free Graphs
- THE CLIQUE-WIDTH OF BIPARTITE GRAPHS IN MONOGENIC CLASSES
- Three Complexity Results on Coloring P k -Free Graphs
- A Certifying Algorithm for 3-Colorability of P 5-Free Graphs
- On graphs with polynomially solvable maximum-weight clique problem
- A New Algorithm for Generating All the Maximal Independent Sets
- Graph colorings with local constraints -- a survey
This page was built for publication: Determining the chromatic number of triangle-free \(2P_3\)-free graphs in polynomial time
