Graph classes with and without powers of bounded clique-width

FLAVIA BONOMO; LUCIANO NORBERTO GRIPPO; MARTIN MILANIC; MARTÍN DARÍO SAFE

DISCRETE APPLIED MATHEMATICS

ELSEVIER SCIENCE BV

Lugar: Amsterdam; Año: 2016 vol. 199 p. 3 - 15

0166-218X

We initiate the study of graph classes of power-bounded clique-width, that is, graph classes for which there exist integers k and ℓ such that the kkth powers of the graphs are of clique-width at most ℓ. We give sufficient and necessary conditions for this property. As our main results, we characterize graph classes of power-bounded clique-width within classes defined by either one forbidden induced subgraph, or by two connected forbidden induced subgraphs. We also show that for every positive integer kk, there exists a graph class such that the kkth powers of graphs in the class form a class of bounded clique-width, while this is not the case for any smaller power.