文章基本信息

标题：Structural Parameterizations of Clique Coloring
本地全文：下载
作者：Lars Jaffke ; Paloma T. Lima ; Geevarghese Philip 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：170
页码：49:1-49:15
DOI：10.4230/LIPIcs.MFCS.2020.49
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：clique coloring; treewidth; clique-width; structural parameterization; Strong Exponential Time Hypothesis