Autor(es)

Flavia Bonomo and Luciano N Grippo and Martin Milanic and Martın Darıo Safe

URL Pública

Abstract

Clique-width is a graph parameter with many algorithmic applications. For a positive integer k, the k-th power of a graph G is the graph with the same vertex set as G, in which two distinct vertices are adjacent if and only if they are at distance at most k in G. Many graph algorithmic problems can be expressed in terms of graph powers. We initiate the study of graph classes of power-bounded clique-width. A graph class is said to be of power-bounded clique-width if there exists an integer k such that the k-th powers of graphs in the class form a class of bounded cliquewidth. We identify several graph classes of power-unbounded clique-width and give a sufficient condition for clique-width to be power-bounded. Based on this condition, we characterize graph classes of power-bounded clique-width among classes defined by two connected forbidden induced subgraphs. We also show that for every integer k, there exists a graph class of power-bounded clique-width such that the k-th powers of graphs in the class form a class of unbounded clique-width.