Does distance-2 coloring fit in Telle and Proskurowski 's algorithm for partial-k trees? This question is on &quot;Vertex Partitioning Problems&quot; framework of Telle and Proskurowski.
For solving problems in parital $k$-trees (i.e., graphs of bounded treewidth), the &quot;Vertex Partitioning Problems&quot; 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 &quot;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)$&quot; 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 &quot;cofinite&quot; 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.
distance-2 coloring is coloring in the square (d(x,y) &lt;= 2 implies xy an edge in the square). If a graph has tw k, its square has bounded clique-width (see Gurski-Wanke and Suchan-Todinca). See Oum et al. for algorithms as in Proskurowski-Telle for graphs of bounded clique-width.