Graph classes with and without powers of bounded clique-width

DOI10.1016/J.DAM.2015.06.010MaRDI QIDQ896650zbMATH OpenOpenAlexFDO

Authors Flavia Bonomo, Luciano N. Grippo, Martin Milanič, Martín D. Safe

Publication date 10 December 2015

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1402.2135

zbMATH Keywords

clique-widthpower of a graphhereditary graph classpower-bounded clique-width

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Distance in graphs (05C12)

Abstract: 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.

Recommendations

• Clique-width of path powers
• A Complete Characterisation of the Linear Clique-Width of Path Powers
• Clique-width of graph classes defined by two forbidden induced subgraphs
• The NLC-width and clique-width for powers of graphs of bounded tree-width
• The Clique-Width of Tree-Power and Leaf-Power Graphs

Cites work

• scientific article; zbMATH DE number 1696534 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 1979486 (Why is no real title available?)
• scientific article; zbMATH DE number 1472167 (Why is no real title available?)
• scientific article; zbMATH DE number 851097 (Why is no real title available?)
• scientific article; zbMATH DE number 2191997 (Why is no real title available?)
• scientific article; zbMATH DE number 3307330 (Why is no real title available?)
• A partial k-arboretum of graphs with bounded treewidth
• Algorithms for vertex-partitioning problems on graphs with fixed clique-width.
• Bounding clique-width via perfect graphs
• Clique-width is NP-complete
• Clique-width of graph classes defined by two forbidden induced subgraphs
• Coloring powers of graphs of bounded clique-width.
• Computing the Tutte Polynomial on Graphs of Bounded Clique‐Width
• Computing the clique-width of large path powers in linear time via a new characterisation of clique-width
• Counting truth assignments of formulas of bounded tree-width or clique-width
• Critical properties of graphs of bounded clique-width
• Diameter increase caused by edge deletion
• Edge dominating set and colorings on graphs with fixed clique-width
• Efficient dominating and edge dominating sets for graphs and hypergraphs
• Exact algorithms for a loading problem with bounded clique width
• Generalized Powers of Graphs and Their Algorithmic Use
• Graph Classes: A Survey
• Graph minors. II. Algorithmic aspects of tree-width
• Handle-rewriting hypergraph grammars
• Hereditary efficiently dominatable graphs
• Interval bigraphs and circular arc graphs
• Latency-bounded target set selection in social networks
• Line graphs of bounded clique-width
• Linear time solvable optimization problems on graphs of bounded clique-width
• Minimal classes of graphs of unbounded clique-width
• On a new class of codes for identifying vertices in graphs
• On powers of graphs of bounded NLC-width (clique-width)
• On the Relationship Between Clique-Width and Treewidth
• On the X-join decomposition for undirected graphs
• On the clique-width of graph with few \(P_{4}\)'s
• On the clique-width of some perfect graph classes
• Polynomial-time recognition of clique-width \(\leq 3\) graphs
• Powers of cycles, powers of paths, and distance graphs
• Recent developments on graphs of bounded clique-width
• The Maximum Independent Set Problem in Planar Graphs
• The tree- and clique-width of bipartite graphs in special classes
• The treewidth and pathwidth of hypercubes
• Transitiv orientierbare Graphen
• Tree-Width and Optimization in Bounded Degree Graphs
• Upper bounds to the clique width of graphs

Cited in

(14)

• The Clique-Width of Tree-Power and Leaf-Power Graphs
• On the width of regular classes of finite structures
• The NLC-width and clique-width for powers of graphs of bounded tree-width
• Clustering powers of sparse graphs
• Colouring diamond-free graphs
• Bounding clique-width via perfect graphs
• Characterization of classical graph classes by weighted clique graphs
• Clique-width for graph classes closed under complementation
• Clique-width of graph classes defined by two forbidden induced subgraphs
• On the powers of graphs with bounded asteroidal number
• Computing the clique-width of cactus graphs
• Bounding clique-width via perfect graphs
• Clique-width of path powers
• Bounding the clique-width of \(H\)-free split graphs

This page was built for publication: Graph classes with and without powers of bounded clique-width

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q896650)