Clique-width of path powers

摘要

We describe the clique-width of path powers by an exact formula, depending only on the number of vertices and the clique number. As a consequence, the clique-width of path powers can be computed in linear time. Path powers are a graph class of unbounded clique-width. Prior to our result, square grids constituted the only known graph class of unbounded clique-width with a similar result. We also show that clique-width and linear clique-width coincide on path powers. (C) 2016 Elsevier B.V. All rights reserved.