Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
419235 | Discrete Applied Mathematics | 2016 | 11 Pages |
Abstract
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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Pinar Heggernes, Daniel Meister, Charis Papadopoulos, Udi Rotics,