Graph classes with and without powers of bounded clique-width
From MaRDI portal
Publication:896650
DOI10.1016/j.dam.2015.06.010zbMath1326.05104arXiv1402.2135OpenAlexW1685365922MaRDI QIDQ896650
Flavia Bonomo-Braberman, Martin Milanič, Martín D. Safe, Luciano N. Grippo
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
Distance in graphs (05C12) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items
Colouring diamond-free graphs, Clique-Width of Graph Classes Defined by Two Forbidden Induced Subgraphs, Bounding clique-width via perfect graphs, Clique-Width for Graph Classes Closed under Complementation, Computing the clique-width of cactus graphs, Bounding Clique-Width via Perfect Graphs, Bounding the clique-width of \(H\)-free split graphs, On the width of regular classes of finite structures
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Polynomial-time recognition of clique-width \(\leq 3\) graphs
- Powers of cycles, powers of paths, and distance graphs
- Minimal classes of graphs of unbounded clique-width
- The treewidth and pathwidth of hypercubes
- Recent developments on graphs of bounded clique-width
- On the X-join decomposition for undirected graphs
- A partial k-arboretum of graphs with bounded treewidth
- Edge dominating set and colorings on graphs with fixed clique-width
- Algorithms for vertex-partitioning problems on graphs with fixed clique-width.
- Critical properties of graphs of bounded clique-width
- Linear time solvable optimization problems on graphs of bounded clique-width
- Upper bounds to the clique width of graphs
- Handle-rewriting hypergraph grammars
- On powers of graphs of bounded NLC-width (clique-width)
- Latency-bounded target set selection in social networks
- Line graphs of bounded clique-width
- Counting truth assignments of formulas of bounded tree-width or clique-width
- Bounding Clique-Width via Perfect Graphs
- Exact Algorithms for a Loading Problem with Bounded Clique Width
- Clique-Width of Graph Classes Defined by Two Forbidden Induced Subgraphs
- Computing the Clique-Width of Large Path Powers in Linear Time via a New Characterisation of Clique-Width
- Tree-Width and Optimization in Bounded Degree Graphs
- Clique-Width is NP-Complete
- The Maximum Independent Set Problem in Planar Graphs
- Graph minors. II. Algorithmic aspects of tree-width
- Diameter increase caused by edge deletion
- Graph Classes: A Survey
- On a new class of codes for identifying vertices in graphs
- Interval bigraphs and circular arc graphs
- Efficient Dominating and Edge Dominating Sets for Graphs and Hypergraphs
- ON THE CLIQUE–WIDTH OF GRAPH WITH FEW P4'S
- ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
- On the Relationship Between Clique-Width and Treewidth
- Hereditary Efficiently Dominatable Graphs
- Computing the Tutte Polynomial on Graphs of Bounded Clique‐Width
- Transitiv orientierbare Graphen
- Generalized Powers of Graphs and Their Algorithmic Use
- Graph-Theoretic Concepts in Computer Science
