期刊
THEORETICAL COMPUTER SCIENCE
卷 412, 期 29, 页码 3487-3500出版社
ELSEVIER SCIENCE BV
DOI: 10.1016/j.tcs.2011.02.038
关键词
Clique coloring; Choosability; Complexity; Polynomial hierarchy
资金
- ERC
- Alexander von Humboldt Foundation
- Hungarian National Research Fund [OTKA 67651]
A k-clique-coloring of a graph G is an assignment of k colors to the vertices of G such that every maximal (i.e., not extendable) clique of G contains two vertices with different colors. We show that deciding whether a graph has a k-clique-coloring is Sigma(p)(2)-complete for every k >= 2. The complexity of two related problems are also considered. A graph is k-clique-choosable, if for every k-list-assignment on the vertices, there is a clique coloring where each vertex receives a color from its list. This problem turns out to be Pi(p)(3)-complete for every k >= 2. A graph G is hereditary k-clique-colorable if every induced subgraph of G is k-clique-colorable. We prove that deciding hereditary k-clique-colorability is also Pi(p)(3)-complete for every k >= 3. Therefore, for all the problems considered in the paper, the obvious upper bound on the complexity turns out to be the exact class where the problem belongs. (C) 2011 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据