<p>I think 2-clique-coloring [GT19 in <a href="http://ls2-www.cs.uni-dortmund.de/lehre/winter200506/ktea/papers/phcom.ps" rel="nofollow">Schaefer and Umans</a>] is an example. The question is whether the given graph can be (improperly) 2-colored in such a way that none of its maximal cliques are monochromatic. For graphs of bounded treewidth, each maximal clique should occur within a single bag of the tree decomposition, so it should work to use the standard dynamic programming approach in which the states of the dynamic program are 2-colorings of the bag that correctly color all maximal cliques within the bag and are consistent with good states of the child bags.</p>

CC BY-SA 3.0
2011-10-18T07:04:08.790Z
It is in P for TW(<=k) for also this reason: the k-clique colouring is MS-expressible: "Exists X_1,...X_k (Partition(X_1,...,X_k) and ForAll X(CliqueMax(X) => not (Exists X_i (Forall x in X( x in X_i)))))
M. kanté
CC BY-SA 3.0
2011-10-18T13:05:36.727Z
I think you mean $\exists X_1, \dots, X_k: (\text{IsPartition}(X_1, \dots, X_k) \land \forall X: (\text{MaxClique}(X) \implies \lnot(\exists X_i: \forall x\in X: x\in X_i)))$
Jeffε
CC BY-SA 3.0
2011-10-17T23:05:47.140Z
2011-10-17T23:05:47.140Z
David Eppstein
<p>List Chromatic Number (Is it true that the graph has a vertex coloring whenever every vertex gets a list of k admissible colors?) is a $\Pi_2^P$-complete problem, but linear-time solvable on bounded-treewidth graphs:</p>

<p><a href="http://www.ii.uib.no/~daniello/papers/EqColoring.pdf">http://www.ii.uib.no/~daniello/papers/EqColoring.pdf</a></p>

CC BY-SA 3.0
2011-10-21T08:55:52.590Z
If you like this result then maybe you're also intested in the following paper: http://arxiv.org/abs/1110.4077 . It appeared on the arXiv this week, and the authors show that List Edge Chromatic Number and List Total Chromatic Number are also linear-time solvable for graphs of bounded treewidth.
Bart Jansen
CC BY-SA 3.0
2011-10-20T08:56:12.467Z
2011-10-20T08:56:12.467Z
Daniel Marx
<p>I'm looking for a problem which belongs to <a href="http://en.wikipedia.org/wiki/Polynomial_hierarchy">$\mathsf{\Sigma^P_2}$</a> in general graphs but is in $\mathsf{P}$ in bounded tree width graphs, In fact I think this problems are harder than using normal dynamic programming in bounded-treewidth graphs to solve them.</p>

CC BY-SA 3.0
2011-10-17T20:30:25.837Z
If the problem is in P for bounded-treewidth graphs, why do you say it's "harder than using normal DP" in such graphs ?
Suresh Venkat
<cc.complexity-theory><graph-theory><treewidth>
Is there any problem in $\mathsf{\Sigma^P_2}$ which is solvable in bounded tree width graphs?
Saeed
# Is there any problem in $\mathsf{\Sigma^P_2}$ which is solvable in bounded tree width graphs?

(Asked by: username_0 on 2011-10-17)

I'm looking for a problem which belongs to [$\mathsf{\Sigma^P\_2}$](http://en.wikipedia.org/wiki/Polynomial_hierarchy) in general graphs but is in $\mathsf{P}$ in bounded tree width graphs, In fact I think this problems are harder than using normal dynamic programming in bounded-treewidth graphs to solve them.

**Tags:** cc.complexity-theory, graph-theory, treewidth

> **Comments:**
> **username_1**: If the problem is in P for bounded-treewidth graphs, why do you say it's "harder than using normal DP" in such graphs ?  

---

## 2 answers

### Answer by username_5 on 2011-10-20. Score: 11 | Accepted answer

List Chromatic Number (Is it true that the graph has a vertex coloring whenever every vertex gets a list of k admissible colors?) is a $\Pi\_2^P$-complete problem, but linear-time solvable on bounded-treewidth graphs:

<http://www.ii.uib.no/~daniello/papers/EqColoring.pdf>

> **Comments:**
> **username_6**: If you like this result then maybe you're also intested in the following paper: http://arxiv.org/abs/1110.4077 . It appeared on the arXiv this week, and the authors show that List Edge Chromatic Number and List Total Chromatic Number are also linear-time solvable for graphs of bounded treewidth.  

---

### Answer by username_2 on 2011-10-17. Score: 13

I think 2-clique-coloring [GT19 in [Schaefer and Umans](http://ls2-www.cs.uni-dortmund.de/lehre/winter200506/ktea/papers/phcom.ps)] is an example. The question is whether the given graph can be (improperly) 2-colored in such a way that none of its maximal cliques are monochromatic. For graphs of bounded treewidth, each maximal clique should occur within a single bag of the tree decomposition, so it should work to use the standard dynamic programming approach in which the states of the dynamic program are 2-colorings of the bag that correctly color all maximal cliques within the bag and are consistent with good states of the child bags.

> **Comments:**
> **username_3**: It is in P for TW(<=k) for also this reason: the k-clique colouring is MS-expressible: "Exists X_1,...X_k (Partition(X_1,...,X_k) and ForAll X(CliqueMax(X) => not (Exists X_i (Forall x in X( x in X_i)))))  
> **username_4**: I think you mean $\exists X_1, \dots, X_k: (\text{IsPartition}(X_1, \dots, X_k) \land \forall X: (\text{MaxClique}(X) \implies \lnot(\exists X_i: \forall x\in X: x\in X_i)))$  

---

