Artículos de revistas
Graph classes with and without powers of bounded clique-width
Fecha
2016-01Registro en:
Bonomo, Flavia; Grippo, Luciano Norberto; Milanič, Martin; Safe, Martin Dario; Graph classes with and without powers of bounded clique-width; Elsevier Science; Discrete Applied Mathematics; 199; 1-2016; 3-15
0166-218X
CONICET Digital
CONICET
Autor
Bonomo, Flavia
Grippo, Luciano Norberto
Milanič, Martin
Safe, Martin Dario
Resumen
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 kth 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 k, there exists a graph class such that the kth powers of graphs in the class form a class of bounded clique-width, while this is not the case for any smaller power.