On the complexity of coloring ( r , ℓ ) ‐graphs

An ( r , ℓ ) ‐graph is a graph that can be partitioned into r independent sets and ℓ 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 ℓ of ( r , ℓ ) ‐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 , ℓ )‐graphs under the parameterized complexity perspective. We show that given a (2, 1)‐partitionS 1 , S 2 , K 1of 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 { | S 1 | , | S 2 | } ; fixed‐parameter tractable ( FPT ) and admits a polynomial kernel when parameterized by max { | S 1 | , | S 2 | } . 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.