1. Structural Parameterizations of Clique Coloring
- Author
-
Paloma T. Lima, Lars Jaffke, and Geevarghese Philip
- Subjects
FOS: Computer and information sciences ,clique coloring ,General Computer Science ,Matching (graph theory) ,Parameterized complexity ,G.2.2 ,Computational Complexity (cs.CC) ,Star (graph theory) ,Clique (graph theory) ,Upper and lower bounds ,Combinatorics ,Tree (descriptive set theory) ,structural parameterization ,Computer Science::Discrete Mathematics ,Computer Science - Data Structures and Algorithms ,FOS: Mathematics ,treewidth ,Mathematics - Combinatorics ,Data Structures and Algorithms (cs.DS) ,Mathematics ,F.2.2 ,Exponential time hypothesis ,Applied Mathematics ,05C85, 68Q25 ,Strong Exponential Time Hypothesis ,Computer Science Applications ,Computer Science - Computational Complexity ,Mathematics of computing → Graph coloring ,Graph (abstract data type) ,Combinatorics (math.CO) ,clique-width - 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 \ge 2$$ q ≥ 2 , we give an $$\mathscr {O}^{\star }(q^{{\mathsf {tw}}})$$ O ⋆ ( q tw ) -time algorithm when the input graph is given together with one of its tree decompositions of width $${\mathsf {tw}} $$ 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 $$\mathsf {XP}$$ XP parameterized by clique-width.
- Published
- 2021