On the complexity of cd-coloring of graphs
| Autor: | M. A. Shalu, S. Vijayakumar, T P Sandhya |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Vertex (graph theory)
Applied Mathematics 0211 other engineering and technologies Induced subgraph 021107 urban & regional planning 0102 computer and information sciences 02 engineering and technology 01 natural sciences Graph Combinatorics 010201 computation theory & mathematics Chordal graph Bipartite graph Discrete Mathematics and Combinatorics Partition (number theory) Time complexity Mathematics |
| Zdroj: | Discrete Applied Mathematics. 280:171-185 |
| ISSN: | 0166-218X |
| DOI: | 10.1016/j.dam.2018.03.004 |
| Popis: | A partition of the vertex set of a graph G into k independent sets V 1 , V 2 , … , V k is called a k -class domination coloring ( k -cd-coloring) of G if for every V i , 1 ≤ i ≤ k , there exists a vertex x i such that V i ⊆ N [ x i ] . For a given graph G and a positive integer k , the cd-colorability problem, CD-Colorability , is to decide whether G admits a k -cd-coloring. This problem is NP-complete, even for bipartite graphs. In this paper, we study the complexity of this problem on several natural graph classes. We prove that CD-Colorability is NP-complete for chordal graphs. We also obtain the following dichotomy results: (i) CD-Colorability is NP-complete for graphs with α ( G ) ≥ 3 and is polynomial time solvable for graphs with α ( G ) ≤ 2 ; (ii) CD-Colorability of K 1 , p -free graphs is NP-complete for p ≥ 4 and is polynomial time solvable for p ≤ 3 ; (iii) CD-Colorability for the class of H -free graphs is polynomial time solvable if H is an induced subgraph of P 4 or P 3 ∪ K 1 or K 1 , 3 and NP-complete for any other H . We present polynomial time algorithms for the classes of claw-free graphs, P 4 -free graphs, and double-split graphs. We also characterize the class of all 3-cd-colorable graphs and thereby improve the time complexity of an algorithm of Merouane et al. (2015) for recognizing 3-cd-colorable graphs from O ( n 6 ) to O ( n 5 ) , where n = | V ( G ) | . |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect