Coloring vertices of claw-free graphs in three colors

DOI10.1007/S10878-012-9577-5MaRDI QIDQ2251141zbMATH OpenOpenAlexFDO

Authors Vadim Lozin, Christopher Purcell

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

zbMATH Keywords

NP-completenesspolynomial-time algorithmclaw-free graphsvertex 3-colorability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coloring of graphs and hypergraphs (05C15) Structural characterization of families of graphs (05C75)

Recommendations

• scientific article; zbMATH DE number 5179133
• Claw-free graphs. VI: Colouring
• Coloring Claw-Free Graphs with $\Delta-1$ Colors
• Clique-coloring claw-free graphs
• On coloring a class of claw-free graphs.
• Colouring squares of claw-free graphs
• Colouring squares of claw-free graphs
• Total coloring of claw-free planar graphs
• On coloring a class of claw-free and hole-twin-free graphs
• Blocks in graphs of a class of claw-free and 3-colorable graphs

Cites work

• scientific article; zbMATH DE number 3290993 (Why is no real title available?)
• scientific article; zbMATH DE number 5179133 (Why is no real title available?)
• 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
• 3-colorability and forbidden subgraphs. I: Characterizing pairs
• 3-coloring and 3-clique-ordering of locally connected graphs
• A combinatorial algorithm for minimum weighted colorings of claw-free perfect graphs
• Coloring edges and vertices of graphs without short or long cycles
• Independence and upper irredundance in claw-free graphs
• Linear time solvable optimization problems on graphs of bounded clique-width
• On the Band-, Tree-, and Clique-Width of Graphs with Bounded Vertex Degree
• On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
• The 3-Colorability Problem on Graphs with Maximum Degree Four
• The NP-Completeness of Edge-Coloring
• The structure of claw-free graphs
• Three-colourability and forbidden subgraphs. II: Polynomial algorithms
• Treewidth for graphs with small chordality
• Vertex colouring and forbidden subgraphs -- a survey

Cited in

(8)

• Blocks in graphs of a class of claw-free and 3-colorable graphs
• On colouring \((2P_2,H)\)-free and \((P_5,H)\)-free graphs
• The vertex colourability problem for \(\{\text{claw}, \text{butterfly}\}\)-free graphs is polynomial-time solvable
• The 2nd-order conditional 3-coloring of claw-free graphs
• A survey on the computational complexity of coloring graphs with forbidden subgraphs
• An intractability result for the vertex 3-colourability problem
• scientific article; zbMATH DE number 5179133 (Why is no real title available?)
• Clustered 3-colouring graphs of bounded degree

This page was built for publication: Coloring vertices of claw-free graphs in three colors

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