License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2021.43
URN: urn:nbn:de:0030-drops-136881
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/13688/
Go to the corresponding LIPIcs Volume Portal

Jaffke, Lars ; Lima, Paloma T. ; Lokshtanov, Daniel

b-Coloring Parameterized by Clique-Width

pdf-format:
LIPIcs-STACS-2021-43.pdf (0.8 MB)

Abstract

We provide a polynomial-time algorithm for b-Coloring on graphs of constant clique-width. This unifies and extends nearly all previously known polynomial-time results on graph classes, and answers open questions posed by Campos and Silva [Algorithmica, 2018] and Bonomo et al. [Graphs Combin., 2009]. This constitutes the first result concerning structural parameterizations of this problem. We show that the problem is FPT when parameterized by the vertex cover number on general graphs, and on chordal graphs when parameterized by the number of colors. Additionally, we observe that our algorithm for graphs of bounded clique-width can be adapted to solve the Fall Coloring problem within the same runtime bound. The running times of the clique-width based algorithms for b-Coloring and Fall Coloring are tight under the Exponential Time Hypothesis.

BibTeX - Entry

@InProceedings{jaffke_et_al:LIPIcs.STACS.2021.43,
  author =	{Jaffke, Lars and Lima, Paloma T. and Lokshtanov, Daniel},
  title =	{{b-Coloring Parameterized by Clique-Width}},
  booktitle =	{38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)},
  pages =	{43:1--43:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-180-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{187},
  editor =	{Bl\"{a}ser, Markus and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/13688},
  URN =		{urn:nbn:de:0030-drops-136881},
  doi =		{10.4230/LIPIcs.STACS.2021.43},
  annote =	{Keywords: b-Coloring, clique-width, vertex cover, structural parameterization}
}

Keywords: b-Coloring, clique-width, vertex cover, structural parameterization
Collection: 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)
Issue Date: 2021
Date of publication: 10.03.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI