Structural Parameterizations of Clique Coloring

DOI10.4230/LIPICS.MFCS.2020.49MaRDI QIDQ6340398arXivFDO

Authors Lars Jaffke, Paloma T. Lima, Geevarghese Philip

Publication date 10 May 2020

Published in arXiv

Full work available at URL https://doi.org/10.4230/LIPICS.MFCS.2020.49

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10)

arXiv classification

cs.CCcs.DSmath.CO

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 $qge2$, we give an $mathcal{O}^{star}(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.

This page was built for publication: Structural Parameterizations of Clique Coloring

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6340398)