✦ LIBER ✦

Tree-decompositions, tree-representability and chordal graphs

✍ Scribed by Reinhard Diestel

Publisher: Elsevier Science
Year: 1988
Tongue: English
Weight: 427 KB
Volume: 71
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(88)90071-4

No coin nor oath required. For personal study only.

✦ Synopsis

The following assertions are shown to be equivalent, for any countable graph G: (1) G can be represented as the intersection graph of a family of subtrees of a tree; (2) G admits a tree-decomposition (Robertson/Seymour) into primes; (3) G is chordal, and G admits a simpkial tree-decomposition (Halin) into primes; (4) G is chordal, and neither of two specSed graphs is contained in G as a simplicial minor.

📜 SIMILAR VOLUMES

On the tree representation of chordal gr

On the tree representation of chordal graphs

✍ Yukio Shibata 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 344 KB 👁 1 views

Representations of chordal graphs as sub

Representations of chordal graphs as subtrees of a tree

✍ James R. Walter 📂 Article 📅 1978 🏛 John Wiley and Sons 🌐 English ⚖ 140 KB 👁 1 views

Strong clique trees, neighborhood trees,

Strong clique trees, neighborhood trees, and strongly chordal graphs

✍ McKee, Terry A. 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 137 KB 👁 1 views

Maximal complete subgraphs and clique trees are basic to both the theory and applications of chordal graphs. A simple notion of strong clique tree extends this structure to strongly chordal graphs. Replacing maximal complete subgraphs with open or closed vertex neighborhoods discloses new relationsh

Distance Approximating Trees for Chordal

Distance Approximating Trees for Chordal and Dually Chordal Graphs

✍ Andreas Brandstädt; Victor Chepoi; Feodor Dragan 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 165 KB

In this paper we show that, for each chordal graph G, there is a tree T such that T is a spanning tree of the square G 2 of G and, for every two vertices, the distance between them in T is not larger than the distance in G plus 2. Moreover, we prove that, if G is a strongly chordal graph or even a d

Tree decomposition of graphs

✍ Raphael Yuster 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 207 KB 👁 1 views

with ␦ G G V r2 q 10 h V log V , and h y 1 divides E , then there is a decomposition of the edges of G into copies of H. This result is asymptotically the best possible for all trees with at least three vertices.

Improved Bandwidth Approximation for Tre

Improved Bandwidth Approximation for Trees and Chordal Graphs

✍ Anupam Gupta 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 110 KB

A linear arrangement of an n-vertex graph G = V E is a one-one mapping f of the vertex set V onto the set n = 0 1 n -1 . The bandwidth of this linear arrangement is the maximum difference between the images of the endpoints of any edge in E G . When the input graph G is a tree, the best known approx