The Clique-Width of Tree-Power and Leaf-Power Graphs

DOI10.1007/978-3-540-74839-7_8MaRDI QIDQ3508556zbMATH OpenOpenAlexFDO

Authors Frank Gurski, Egon Wanke

Publication date 1 July 2008

Published in Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-74839-7_8

zbMATH Keywords

clique-widthtree-widthleaf powersNLC-widthtree powersstrictly chordal

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• The NLC-width and clique-width for powers of graphs of bounded tree-width
• Leaf Powers and Their Properties: Using the Trees
• Graph classes with and without powers of bounded clique-width
• On powers of graphs of bounded NLC-width (clique-width)
• Clique-width of path powers

Cites work

• scientific article; zbMATH DE number 1472167 (Why is no real title available?)
• Algorithms for Square Roots of Graphs
• Coloring powers of graphs of bounded clique-width.
• Computing roots of graphs is hard
• Graph Classes: A Survey
• Graph minors. II. Algorithmic aspects of tree-width
• Graph-Theoretic Concepts in Computer Science
• Linear time solvable optimization problems on graphs of bounded clique-width
• Linear-Time Algorithms for Tree Root Problems
• Monadic second-order evaluations on tree-decomposable graphs
• On graph powers for leaf-labeled trees
• On simple characterizations of k-trees
• On the Relationship Between Clique-Width and Treewidth
• Some remarks about leaf roots
• Strictly chordal graphs are leaf powers
• Structure and linear time recognition of 3-leaf powers
• Structure and linear-time recognition of 4-leaf powers
• Upper bounds to the clique width of graphs
• \(k\)-NLC graphs and polynomial algorithms

Cited in

(9)

• Clique-width of path powers
• On powers of graphs of bounded NLC-width (clique-width)
• The NLC-width and clique-width for powers of graphs of bounded tree-width
• Graph classes with and without powers of bounded clique-width
• Parameterized leaf power recognition via embedding into graph products
• Ptolemaic Graphs and Interval Graphs Are Leaf Powers
• Parameterized leaf power recognition via embedding into graph products
• A Complete Characterisation of the Linear Clique-Width of Path Powers
• Tree-width, clique-minors, and eigenvalues.

This page was built for publication: The Clique-Width of Tree-Power and Leaf-Power Graphs

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