✦ LIBER ✦

Vertex partitions of chordal graphs

✍ Scribed by David R. Wood

Publisher: John Wiley and Sons
Year: 2006
Tongue: English
Weight: 103 KB
Volume: 53
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20183

No coin nor oath required. For personal study only.

✦ Synopsis

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 prove that for all k ≥ ℓ ≥ 0, every k‐tree has an ℓ‐tree‐partition in which each bag induces a connected ${\lfloor k} /(\ell+1) \rfloor$‐tree. An analogous result is proved for oriented k‐trees. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 167–172, 2006

📜 SIMILAR VOLUMES

Vertex Partitions by Connected Monochrom

Vertex Partitions by Connected Monochromatic k-Regular Graphs

✍ Gábor N. Sárközy; Stanley M. Selkow 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 135 KB

A generalization of chordal graphs

✍ P. D. Seymour; R. W. Weaver 📂 Article 📅 1984 🏛 John Wiley and Sons 🌐 English ⚖ 487 KB

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 t

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.

On vertex partitions and some minor-mono

On vertex partitions and some minor-monotone graph parameters

✍ D. Gonçalves 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 107 KB

We study vertex partitions of graphs according to some minormonotone graph parameters. Ding et al. [J Combin Theory Ser B 79(2) (2000), 221-246] proved that some minor-monotone parameters are such that, any graph G with (G) ≥ 2 admits a vertex partition into two graphs with parameter at most (G)-1.

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

Star partitions of graphs

✍ Egawa, Y.; Kano, M.; Kelmans, Alexander K. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 78 KB 👁 2 views

Let G be a graph and n ≥ 2 an integer. We prove that the following are equivalent: (i) there is a partition , and (ii) for every subset S of V (G), G \ S has at most n|S| components with the property that each of their blocks is an odd order complete graph.