The 2nd-order conditional 3-coloring of claw-free graphs

DOI10.1016/j.tcs.2008.01.034zbMath1146.68059OpenAlexW2028854762MaRDI QIDQ924141

Wenli Zhou, Xue Liang Li

Publication date: 28 May 2008

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2008.01.034

zbMATH Keywords

claw-free graphlinear time algorithmNP-completevertex-coloring2nd-order conditional chromatic number2nd-order conditional-coloring

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (13)

Graph \(r\)-hued colorings -- a survey ⋮ Unnamed Item ⋮ On the complexity of injective colorings and its generalizations ⋮ The $r$-dynamic edge coloring of a closed helm graph ⋮ On the difference between chromatic number and dynamic chromatic number of graphs ⋮ Upper bounds for the 2-hued chromatic number of graphs in terms of the independence number ⋮ δ-Dynamic chromatic number of Helm graph families ⋮ On dynamic coloring of certain cycle-related graphs ⋮ Unnamed Item ⋮ \(r\)-Dynamic chromatic number of some line graphs ⋮ On r- dynamic coloring of the family of bistar graphs ⋮ On the r-dynamic coloring of the direct product of a path and a k-subdivision of a star graph ⋮ On r− dynamic coloring of the gear graph families

Cites Work

• Complexity of conditional colorability of graphs
• Conditional colorings of graphs
• The NP-Completeness of Edge-Coloring
• Unnamed Item
• Unnamed Item

This page was built for publication: The 2nd-order conditional 3-coloring of claw-free graphs