Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
420930 | Discrete Applied Mathematics | 2007 | 9 Pages |
Abstract
Given a graph G , the graph GlGl has the same vertex set and two vertices are adjacent in GlGl 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 GlGl, 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 GlGl is at most 2(l+1)nlcw(G)2(l+1)nlcw(G).
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Karol Suchan, Ioan Todinca,