Coloring vertices of claw-free graphs in three colors
From MaRDI portal
Publication:2251141
DOI10.1007/s10878-012-9577-5zbMath1302.05057OpenAlexW1968293901MaRDI QIDQ2251141
Christopher Purcell, Vadim V. Lozin
Publication date: 11 July 2014
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10878-012-9577-5
Analysis of algorithms and problem complexity (68Q25) Structural characterization of families of graphs (05C75) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (2)
On colouring \((2P_2,H)\)-free and \((P_5,H)\)-free graphs ⋮ A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs
Cites Work
- On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
- Treewidth for graphs with small chordality
- Independence and upper irredundance in claw-free graphs
- 3-colorability and forbidden subgraphs. I: Characterizing pairs
- 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
- Three-colourability and forbidden subgraphs. II: Polynomial algorithms
- Vertex colouring and forbidden subgraphs -- a survey
- Linear time solvable optimization problems on graphs of bounded clique-width
- A combinatorial algorithm for minimum weighted colorings of claw-free perfect graphs
- The NP-Completeness of Edge-Coloring
- The 3-Colorability Problem on Graphs with Maximum Degree Four
- 3-coloring and 3-clique-ordering of locally connected graphs
- On the Band-, Tree-, and Clique-Width of Graphs with Bounded Vertex Degree
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Coloring vertices of claw-free graphs in three colors
