Graphs of Power-Bounded Clique-Width

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

Santorini

Workshop; Workshop on Graph Classes, Optimization, and Width Parameters (GROW); 2013

Clique-width is a graph parameter with many algorithmic applications. A $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 introduce and study the notion of graph classes of power-bounded clique-width. A graph class is 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 clique-width. 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.