A Lower Bound of the cd-Chromatic Number and Its Complexity

DOI10.1007/978-3-319-53007-9_30zbMath1485.68200OpenAlexW2583392881MaRDI QIDQ2971664

No author found.

Publication date: 7 April 2017

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

Full work available at URL: https://doi.org/10.1007/978-3-319-53007-9_30

zbMATH Keywords

cliquecd-coloringsubclique

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (6)

On cd-coloring of trees and co-bipartite graphs ⋮ Parameterized and exact algorithms for class domination coloring ⋮ On the complexity of cd-coloring of graphs ⋮ On cd-coloring of \(\{P_5,K_4\}\)-free chordal graphs ⋮ On CD-chromatic number and its lower bound in some classes of graphs ⋮ On the algorithmic aspects of strong subcoloring

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• On the complexity of approximating \(k\)-set packing
• The cd-Coloring of Graphs
• On the dominator colorings in trees
• Parameterized and Exact Algorithms for Class Domination Coloring
• A survey of graph coloring - its types, methods and applications
• Algorithmic Aspects of Dominator Colorings in Graphs
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph

This page was built for publication: A Lower Bound of the cd-Chromatic Number and Its Complexity