# Is there any problem in $\mathsf{\Sigma^P_2}$ which is solvable in bounded tree width graphs?

I'm looking for a problem which belongs to $\mathsf{\Sigma^P_2}$ 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.

-
 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♦ Oct 17 '11 at 20:30

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

-
Very nice thanks, it seems it's better than David answer for me, let me read it. – Saeed Oct 20 '11 at 19:57
If you like this result then maybe you're also intested in the following paper: 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 Oct 21 '11 at 8:55

I think 2-clique-coloring [GT19 in Schaefer and Umans] 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.

-
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é Oct 18 '11 at 7:04
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)))$ – JɛﬀE Oct 18 '11 at 13:05