Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2020.49
URN: urn:nbn:de:0030-drops-127157
URL: https://drops.dagstuhl.de/opus/volltexte/2020/12715/
Jaffke, Lars ; Lima, Paloma T. ; Philip, Geevarghese
Structural Parameterizations of Clique Coloring
| pdf-format: |
|
Abstract
A clique coloring of a graph is an assignment of colors to its vertices such that no maximal clique is monochromatic. We initiate the study of structural parameterizations of the Clique Coloring problem which asks whether a given graph has a clique coloring with q colors. For fixed q ≥ 2, we give an 𝒪^⋆(q^{tw})-time algorithm when the input graph is given together with one of its tree decompositions of width tw. We complement this result with a matching lower bound under the Strong Exponential Time Hypothesis. We furthermore show that (when the number of colors is unbounded) Clique Coloring is XP parameterized by clique-width.
BibTeX - Entry
@InProceedings{jaffke_et_al:LIPIcs:2020:12715,
author = {Lars Jaffke and Paloma T. Lima and Geevarghese Philip},
title = {{Structural Parameterizations of Clique Coloring}},
booktitle = {45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
pages = {49:1--49:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-159-7},
ISSN = {1868-8969},
year = {2020},
volume = {170},
editor = {Javier Esparza and Daniel Kr{\'a}ľ},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12715},
URN = {urn:nbn:de:0030-drops-127157},
doi = {10.4230/LIPIcs.MFCS.2020.49},
annote = {Keywords: clique coloring, treewidth, clique-width, structural parameterization, Strong Exponential Time Hypothesis}
}
| Keywords: | clique coloring, treewidth, clique-width, structural parameterization, Strong Exponential Time Hypothesis | |
| Seminar: | 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020) | |
| Issue date: | 2020 | |
| Date of publication: | 18.08.2020 |
