Premium
On the complexity of coloring ( r , ℓ ) ‐graphs
Author(s) -
Alves Matheus S. D.,
Nascimento Julliano R.,
Souza Uéverton S.
Publication year - 2021
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/itor.12938
Subject(s) - combinatorics , parameterized complexity , mathematics , split graph , discrete mathematics , graph coloring , chordal graph , graph , vertex (graph theory) , 1 planar graph
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.