The leafage of a chordal graph
From MaRDI portal
Abstract: The leafage l(G) of a chordal graph G is the minimum number of leaves of a tree in which G has an intersection representation by subtrees. We obtain upper and lower bounds on l(G) and compute it on special classes. The maximum of l(G) on n-vertex graphs is n - lg n - (1/2) lg lg n + O(1). The proper leafage l*(G) is the minimum number of leaves when no subtree may contain another; we obtain upper and lower bounds on l*(G). Leafage equals proper leafage on claw-free chordal graphs. We use asteroidal sets and structural properties of chordal graphs.
Recommendations
Cited in
(43)- Subgraph trees in graph theory
- Parameterized algorithms for Steiner tree and dominating set: bounding the leafage by the vertex leafage
- Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage
- On the tractability of optimization problems on \(H\)-graphs
- Semilattice polymorphisms and chordal graphs
- The vertex leafage of chordal graphs
- On asteroidal sets in chordal graphs
- Characterization of classical graph classes by weighted clique graphs
- An efficient algorithm for counting Markov equivalent DAGs
- Linear algorithms for chordal graphs of bounded directed vertex leafage
- Non-separating cliques, asteroidal number and leafage. The minimal 4-asteroidal split graphs
- A decomposition theorem for chordal graphs and its applications
- k-separator chordal graphs: leafage and subfamilies
- On models of directed path graphs non rooted directed path graphs
- Minimum average distance clique trees
- Extended star graphs
- Characterizing directed path graphs by forbidden asteroids
- Strictly interval graphs: characterization and linear time recognition
- Clique trees of chordal graphs: leafage and 3-asteroidals
- Polynomial-Time Algorithm for the Leafage of Chordal Graphs
- scientific article; zbMATH DE number 1990684 (Why is no real title available?)
- Independent sets in asteroidal triple-free graphs
- Intersection representation of digraphs in trees with few leaves
- scientific article; zbMATH DE number 4114651 (Why is no real title available?)
- On strict-double-bound numbers of graphs and cut sets
- On k-trees with given leafages
- Testing isomorphism of chordal graphs of bounded leafage is fixed-parameter tractable (extended abstract)
- The Neighborhood Polynomial of Chordal Graphs
- Parameterized complexity of multicut in weighted trees
- The diameter of AT‐free graphs
- Recognizing Proper Tree-Graphs
- Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage
- Domination and Cut Problems on Chordal Graphs with Bounded Leafage
- Graphs with at most two moplexes
- Parameterized algorithms for Steiner tree and (connected) dominating set on path graphs
- Approximation ratio of the min-degree greedy algorithm for maximum independent set on interval and chordal graphs
- Testing isomorphism of chordal graphs of bounded leafage is fixed-parameter tractable
- Succinct data structure for chordal graphs with bounded vertex leafage
- Domination and cut problems on chordal graphs with bounded leafage
- Obstructions to faster diameter computation: asteroidal sets
- Succinct data structures for chordal graph with bounded leafage or vertex leafage
- The neighborhood polynomial of chordal graphs
- Asteroidal quadruples in non rooted path graphs
This page was built for publication: The leafage of a chordal graph
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4222379)
