# Does distance-2 coloring fit in Telle and Proskurowski 's algorithm for partial-k trees?

(This question is inteneded for people who have heard of "Vertex Partitioning Problems" framework of Telle and Proskurowski. Others may dig in only if they are interested in practical algorithms for partial-$$k$$ trees.)

For solving problems in parital $$k$$-trees (i.e., graphs of bounded treewidth), the "Vertex Partitioning Problems" framework of Telle and Proskurowski looks promising. This framework gives practical algorithms for some problems (as opposed to MSO). Given a graph $$G$$ and a $$q\times q$$ matrix $$D$$ each entry of which is a subset of $$\{0,1,2,\dots\}$$, the question "Does there exist a partition $$V_1, V_2, \dots ,V_q$$ of $$V(G)$$ such that $$\forall x \in V_i,\; |N(x) \cap V_j| \in D(i,j)$$" is a vertex partitioning problem.

Their paper (Algorithms for vertex partitioning problems on partial k-trees) claim that every vertex partitioning problem is solvable in time polynomial for partial $$k$$-trees (time complexity is like $$\mathcal{O}(nq^{2(k+1)})$$

My doubt is regarding the "cofinite" condition they use. Is this important? Doesn't that mean this method doesn't work (out of box) for distance-2 coloring, since for distance-2 coloring the matrix $$D$$ must consist of entries $$\{0\}$$ along (main) diagonal and entries $$\{0,1\}$$ for off-diagonal.

Note: They explicitly state that the method works for coloring. For coloring also, diagonal entries are same; May be main diagonal is a special case?

Thank you.

• If you did have a look at the pointed papers you would see that what I said for $2$ is true for any fixed $l$. Also, the algorithms by Binh-Minh et al. are also singly exponential in the clique-width. If you want cases that do not work even for tree-width, you can have a look at this paper arxiv.org/abs/1004.2642 Sure, distance-$l$ colouring is moderately exponential for bounded clique-width as $G^l$ has clique-width at most $2(l+1)^{cw(G)}$, and $k$-colouring is a partitionning problem with $0$ on the diagonals and $\mathbb{N}$ in any other entry. – M. kanté Jan 22 at 8:40