Domino treewidth

We consider a special variant of tree-decompositions, called domino tree-decompositions, and the related notion of domino treewidth. In a domino tree-decomposition, each vertex of the graph belongs to at most two nodes of the tree. We prove that for every k, d, there exists a constant C_k,d such that a graph with treewidth at most k and maximum degree at most d has domino treewidth at most C_k,d. The domino treewidth of a tree can be computed in O(n^2 log n) time. There exist polynomial time algorithms that — for fixed k — decide whether a given graph G has domino treewidth at most k. If k is not fixed, this problem is NP-complete. The domino treewidth problem is hard for the complexity classes W[t] for all t in N, and hence the problem for fixed k is unlikely to be solvable in O(n^c ), where c is a constant, not depending on k.