✦ LIBER ✦

A generalization of chordal graphs

✍ Scribed by P. D. Seymour; R. W. Weaver

Publisher: John Wiley and Sons
Year: 1984
Tongue: English
Weight: 487 KB
Volume: 8
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190080206

No coin nor oath required. For personal study only.

✦ Synopsis

In a 3-connected planar triangulation, every circuit of length 2 4 divides the rest of the edges into two nontrivial parts (inside and outside) which are "separated" by the circuit. Neil Robertson asked to what extent triangulations are characterized by this property, and conjectured an answer. In this paper we prove his conjecture, that if G is simple and 3-connected and every circuit of length 3 4 has at least two "bridges," then G may be built up by "clique-sums" starting from complete graphs and planar triangulations. This is a generalization of Dirac's theorem about chordal graphs.

📜 SIMILAR VOLUMES

Vertex partitions of chordal graphs

✍ David R. Wood 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 103 KB

## Abstract A __k‐tree__ is a chordal graph with no (__k__ + 2)‐clique. An ℓ‐__tree‐partition__ of a graph __G__ is a vertex partition of __G__ into ‘bags,’ such that contracting each bag to a single vertex gives an ℓ‐tree (after deleting loops and replacing parallel edges by a single edge). We pro

Chordal Completions of Planar Graphs

✍ F.R.K. Chung; D. Mumford 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 431 KB

We prove that every planar graph on \(n\) vertices is contained in a chordal graph with at most \(c n \log n\) edges for some abolsute constant \(c\) and this is best possible to within a constant factor. 1994 Academic Press, Inc.

Diameters of iterated clique graphs of c

Diameters of iterated clique graphs of chordal graphs

✍ Bor-Liang Chen; Ko-Wei Lih 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 272 KB

## Abstract The clique graph __K__(__G__) of a graph is the intersection graph of maximal cliques of __G.__ The iterated clique graph __K__^__n__^(__G__) is inductively defined as __K__(K^n−1^(__G__)) and __K__^1^(__G__) = __K__(__G__). Let the diameter diam(__G__) be the greatest distance between

On the interval number of a chordal grap

On the interval number of a chordal graph

✍ Edward R. Scheinerman 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 249 KB 👁 2 views

The interval number of a (simple, undirected) graph G is the least positive integer t such that G is the intersection graph of sets, each of which is the union of t real intervals. A chordal (or triangulated) graph is one with no induced cycles on 4 or more vertices. If G is chordal and has maximum

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

The w-median of a connected strongly cho

The w-median of a connected strongly chordal graph

✍ Hai-Yen Lee; Gerard J. Chang 📂 Article 📅 1994 🏛 John Wiley and Sons 🌐 English ⚖ 337 KB 👁 1 views

## Abstract Suppose __G = (V, E)__ is a graph in which every vertex __x__ has a non‐negative real number __w(x)__ as its weight. The __w__‐distance sum of a vertex __y__ is __D~G, w~(y)__ = σ~x≅v~ __d(y, x)w(x).__ The __w__‐median of __G__ is the set of all vertices __y__ with minimum __w__‐distanc