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

  • SCI-E
  • SSCI
作者: Alves, Matheus S. D.;Nascimento, Julliano R.;Souza, Ueverton S.
作者机构: Univ Fed Goias, Inst Informat, Quadra D,Campus Samambaia, BR-74690900 Goiania, Go, Brazil.
Univ Fed Fluminense, Inst Comp, Av Gal Milton Tavares Souza S-N, BR-24210346 Niteroi, RJ, Brazil.
语种: 英文
关键词: colorability;graph coloring;(r, l)-graph;list coloring;bipartite graphs;parameterized complexity
ISSN: 0969-6016
年: 2021
摘要: 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.

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