Journal
DISCRETE APPLIED MATHEMATICS
Volume 155, Issue 14, Pages 1885-1893Publisher
ELSEVIER SCIENCE BV
DOI: 10.1016/j.dam.2007.03.014
Keywords
clique-width; NLC-width; coloring; power graph; polynomial
Categories
Ask authors/readers for more resources
Given a graph G, the graph G(l) has the same vertex set and two vertices are adjacent in Gl 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 G(l), where G is the input graph. We show that, for any fixed value of 1, 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 G(l) is at most 2(l + l)(nlcw)(G). (c) 2007 Elsevier B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available