Anzeige
Erschienen in:
2017 | OriginalPaper | Buchkapitel
A Lower Bound of the cd-Chromatic Number and Its Complexity
verfasst von : M. A. Shalu, S. Vijayakumar, T. P. Sandhya
Erschienen in: Algorithms and Discrete Applied Mathematics
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
The cd-coloring is motivated by the super-peer architecture in peer-to-peer resource sharing technology. A vertex set partition of a graph G into k independent sets \(V_1, V_2, \ldots , V_k\) is called a k-color domination partition (k-cd-coloring) of G if there exists a vertex \(u_i\in V(G)\) such that \(u_i\) dominates \(V_i\) in G for \(1 \le i \le k\) and the smallest integer k for which G admits a k-cd-coloring is called the cd-chromatic number of G, denoted by \(\chi _{cd}(G)\). A subclique is a set S of vertices of a graph G such that for any \(x,y\in S\), \(d(x,y)\ne 2\) in G and the cardinality of a maximum subclique in G is denoted by \(\omega _{s}(G)\). Clearly, \(\omega _{s}(G) \le \chi _{cd}(G)\) for a graph G.
In this paper, we explore the complexity status of Subclique: for a given graph G and a positive integer k, Subclique is to decide whether G has a subclique of size at least k. We prove that Subclique is NP-complete for (i) bipartite graphs, (ii) chordal graphs, and (iii) the class of H-free graphs when H is a fixed graph on 5-vertices. In addition, we prove that Subclique for the class of H-free graphs is polynomial time solvable only if H is an induced subgraph of \(P_4\); otherwise the problem is NP-complete. Moreover, Subclique is polynomial time solvable for trees, split graphs, and co-bipartite graphs.