Graph classes with and without powers of bounded clique-width
| Autor: | Bonomo, Flavia, Grippo, Luciano N., Milanič, Martin, Safe, Martín D. |
|---|---|
| Rok vydání: | 2014 |
| Předmět: | |
| Zdroj: | Discrete Applied Mathematics 199 (2016): 3-15 |
| Druh dokumentu: | Working Paper |
| DOI: | 10.1016/j.dam.2015.06.010 |
| Popis: | We initiate the study of graph classes of power-bounded clique-width, that is, graph classes for which there exist integers $k$ and $\ell$ such that the $k$-th powers of the graphs are of clique-width at most $\ell$. 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 $k$-th powers of graphs in the class form a class of bounded clique-width, while this is not the case for any smaller power. Comment: 23 pages, 4 figures |
| Databáze: | arXiv |
| Externí odkaz: |
|