On the complexity of coloring (r, l)-graphs

An (r, l)-graph is a graph that can be partitioned into r independent sets and l cliques. In the Graph Coloring problem, we are given as input a graph G, and the objective is to determine the minimum integer k such that G admits a proper vertex k-coloring. In this work, we describe a Poly versus NP-hard dichotomy of this problem regarding the parameters r and l of (r, l)-graphs, which determine the boundaries of the NP-hardness of Graph Coloring for such classes. We also analyze the complexity of the problem on (r, l)-graphs under the parameterized complexity perspective. We show that given a (2, 1)-partition S-1,S-2,K-1 of a graph G, finding an optimal coloring of G is NP-complete even when K-1 is a maximal clique of size 3; XP but W[1]-hard when parameterized by min{vertical bar S-1 vertical bar,vertical bar S-2 vertical bar}; fixed-parameter tractable (FPT) and admits a polynomial kernel when parameterized by max{vertical bar S-1 vertical bar,vertical bar S-2 vertical bar}. Besides, concerning the case where K-1 is a maximal clique of size 3, a P versus NPh dichotomy regarding the neighborhood of K-1 is provided; furthermore, an FPT algorithm parameterized by the number of vertices having no neighbor in K-1 is presented.

Automated summary

The text discusses the complexity of Graph Coloring problem on (r, l)-graphs, describing the Poly versus NP-hard dichotomy and parameterized complexity perspective, analyzing different scenarios for finding optimal coloring of graph G. Additionally, it provides a dichotomy regarding the neighborhood of K-1 and presents an FPT algorithm parameterized by the number of vertices without neighbors in K-1.