Elsevier

Discrete Applied Mathematics

Volume 155, Issue 14, 1 September 2007, Pages 1885-1893
Discrete Applied Mathematics

On powers of graphs of bounded NLC-width (clique-width)

https://doi.org/10.1016/j.dam.2007.03.014Get rights and content
Under an Elsevier user license
open archive

Abstract

Given a graph G, the graph Gl 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 Gl, 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 is at most 2(l+1)nlcw(G).

Keywords

Clique-width
NLC-width
Coloring
Power graph
Polynomial

Cited by (0)

A preliminary version of this paper appeared as [10] in: Proceedings of the 29th Workshop on Graph-theoretic Concepts in Computer Science (WG 2003).