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

DOI10.1007/978-3-540-74839-7_8zbMATH Open1141.68531OpenAlexW1538861354MaRDI QIDQ3508556FDOQ3508556

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

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

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)

Cites Work

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

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)