𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Clique-sums, tree-decompositions and compactness

✍ Scribed by Igor Kříž; Robin Thomas

Publisher
Elsevier Science
Year
1990
Tongue
English
Weight
588 KB
Volume
81
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

We develop a technique

for extending excluded minor theorems to infinite graphs, and in particular we answer a question of Neil Robertson.

📜 SIMILAR VOLUMES

Tree-decompositions, tree-representabili
Tree-decompositions, tree-representability and chordal graphs
✍ Reinhard Diestel 📂 Article 📅 1988 🏛 Elsevier Science 🌐 English ⚖ 427 KB

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

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

Surfaces, Tree-Width, Clique-Minors, and
Surfaces, Tree-Width, Clique-Minors, and Partitions
✍ Guoli Ding; Bogdan Oporowski; Daniel P. Sanders; Dirk Vertigan 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 214 KB

In 1971, Chartrand, Geller, and Hedetniemi conjectured that the edge set of a planar graph may be partitioned into two subsets, each of which induces an outerplanar graph. Some partial results towards this conjecture are presented. One such result, in which a planar graph may be thus edge partitione

On resolvable tree-decompositions of com
On resolvable tree-decompositions of complete graphs
✍ Zbigniew Lonc 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 355 KB 👁 1 views

A partition of the edge set of a graph H into subsets inducing graphs H,, . . . , H, isomorphic to a graph G is said to be a G-decomposition of H. A G-decomposition of H is resolvable if the set {H,, . . . , H,} can be partitioned into subsets, called resolution classes, such that each vertex of H

Metric characterizations of proper inter
Metric characterizations of proper interval graphs and tree-clique graphs
✍ Gutierrez, M.; Oubi�a, L. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 393 KB 👁 2 views

A connected graph G is a tree-clique graph if there exists a spanning tree T (a compatible tree) such that every clique of G is a subtree of T. When Tis a path the connected graph G is a proper interval graph which is usually defined as intersection graph of a family of closed intervals of the real