2017/05/25 by Sancrey Rodrigues Alves, Alves, Sancrey R., Konrad K. Dabrowski +9
Computer Science · Engineering · #05C85 #Advanced Graph Theory Research #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #G.2.2 #Graph Labeling and Dimension Problems #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1705.09177
openalex publication_date 2017/05/25 · openalex created_date 2019/06/27 · openalex updated_date 2026/07/28
An (r, ℓ)-partition of a graph G is a partition of its vertex set into r independent sets and ℓ cliques. A graph is (r, ℓ) if it admits an (r, ℓ)-partition. A graph is well-covered if every maximal independent set is also maximum. A graph is (r,ℓ)-well-covered if it is both (r,ℓ) and well-covered. In this paper we consider two different decision problems. In the (r,ℓ)-Well-Covered Graph problem ((r,ℓ)WCG for short), we are given a graph G, and the question is whether G is an (r,ℓ)-well-covered graph. In the Well-Covered (r,ℓ)-Graph problem (WC(r,ℓ)G for short), we are given an (r,ℓ)-graph G together with an (r,ℓ)-partition of V(G) into r independent sets and ℓ cliques, and the question is whether G is well-covered. We classify most of these problems into P, coNP-complete, NP-complete, NP-hard, or coNP-hard. Only the cases WC(r,0)G for r≥ 3 remain open. In addition, we consider the parameterized complexity of these problems for several choices of parameters, such as the size α of a maximum independent set of the input graph, its neighborhood diversity, its clique-width, or the number ℓ of cliques in an (r, ℓ)-partition. In particular, we show that the parameterized problem of deciding whether a general graph is well-covered parameterized by α can be reduced to the WC(0,ℓ)G problem parameterized by ℓ. In addition, we prove that both problems are coW[2]-hard but can be solved in XP-time.