On powers of graphs of bounded NLC-width (clique-width) ?
Given a graph G , the graph Gl G l has the same vertex set and two vertices are adjacent in Gl G l if and only if they are at distance at most l in G. The l -coloring problem consists in finding an optimal vertex coloring of the graph Gl G l , where G is the input graph. We show that, for any fixed value of l, the l -coloring problem is polynomial when restricted to graphs of bounded NLC-width (or clique-width), if an expression of the graph is also part of the input. We also prove that the NLC-width of Gl G l is at most 2(l+1)nlcw(G) 2 ( l + 1 ) nlcw ( G ) .
nlc-width clique-width coloring polynomial power graph