On the complexity of cd-coloring of graphs

DOI10.1016/j.dam.2018.03.004zbMath1439.05093OpenAlexW2885645764MaRDI QIDQ2181255

Yanyan Li

Publication date: 18 May 2020

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2018.03.004

zbMATH Keywords

vertex coloringchordal graphssplit graphsclaw-free graphstotal dominating setcd-coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (6)

On the complexity of minimum \(q\)-domination partization problems ⋮ On cd-coloring of trees and co-bipartite graphs ⋮ Parameterized and exact algorithms for class domination coloring ⋮ On cd-coloring of \(\{P_5,K_4\}\)-free chordal graphs ⋮ On CD-chromatic number and its lower bound in some classes of graphs ⋮ Lower bounds on approximating some variations of vertex coloring problem over restricted graph classes

Cites Work

• The strong perfect graph theorem
• Paw-free graphs
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Dominated colorings of graphs
• The cd-Coloring of Graphs
• Complexity of graph partition problems
• Parameterized and Exact Algorithms for Class Domination Coloring
• A Lower Bound of the cd-Chromatic Number and Its Complexity
• Algorithmic Aspects of Dominator Colorings in Graphs
• The NP-Completeness of Edge-Coloring
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the complexity of cd-coloring of graphs