Excluding a countable clique
type: Item
instance of: scholarly article
title: Excluding a countable clique
zbMATH Open document ID: 0935.05083
author: Reinhard Diestel
author: Robin Thomas
published in: Journal of Combinatorial Theory. Series B
publication date: 2000-05-04T00:00:00Z
review text: Let \(G= (V,E)\) be a simple undirected graph (possibly infinite). \(H\) is a minor of \(G\) if \(G\) contains a family \((V_x)_{x\in V(H)}\) of disjoint connected vertex sets (possibly infinite) such that \(G\) has a \(V_x- V_y\) edge whenever \(xy\) is an edge of \(H\). If \(T\) is a tree and \({\mathcal V}= (V_t)_{t\in T}\) is a family of vertex sets \(V_t\) in \(G\) then the pair \({\mathcal D}= (T,{\mathcal V})\) is called a tree-decomposition of \(G\) if it satisfies three conditions for \(V_t\), given in Chapter 2. Some properties of tree-decompositions which are necessary for the proofs are considered by nine lemmas in Chapter 5. \({\mathcal D}\) is said to have a finite adhesion if the values of \(|V_{t_1}- V_{t_2}|\) for edges \(t_1t_2\in T\) and of \(\liminf_{i\to\infty}|V_{t_i}\cap V_{t_{i+1}}|\) for infinite paths \(t_1t_2\dots\) in \(T\) are always finite. A surface \(S\) is defined to be a compact connected 2-manifold with boundary, and \(S\) is said to be closed if its boundary is empty. The class of all countable graphs that can be nearly embedded in \(S\) is denoted by \({\mathcal F}(S)\). The concept of nearly embedding of \(G\) in \(S\) is defined in Chapter 2, and in Chapter 4 some of its properties are given. The main results of the authors are given by two theorems. The first result is the extension to infinite graphs of the known \(K_n\) excluded minor theorem of Robertson and Seymour (Theorem 2.2). Let \(S_n\) be the orientable (and analogously \(S_n'\) the non-orientable) closed surfaces of highest genus in which \(K_n\) cannot be embedded. Then, for integers \(n\) and \(k\) the following holds: For every \(n\geq 0\) there exists a \(k\geq 0\) such that every (finite or infinite) graph with no \(K_n\) minor has a tree-decomposition over \({\mathcal F}(S_n- k)\cup{\mathcal F}(S_n'- k)\) (Theorem 3.1). Its extensive proof (in Chapter 6) is carried out with the help of a lemma (Lemma 6.1). The second result is a structural characterization of …
Mathematics Subject Classification ID: 05C83
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C69
zbMATH DE Number: 1346887
zbMATH Keywords: minor
zbMATH Keywords: tree-decomposition
reviewed by: Heinz-Joachim Presia
MaRDI profile type: Publication
OpenAlex ID: W2060341104
cites work: Q4342632
cites work: Q3999150
cites work: A compactness theorem for complete separators
cites work: The depth-first search tree structure of \(TK_{\aleph_ 0}\)-free graphs
cites work: Clique-sums, tree-decompositions and compactness
cites work: Graphs on surfaces
cites work: Graph minors. XVI: Excluding a non-planar graph
cites work: Excluding infinite minors
cites work: Excluding Subdivisions of Infinite Cliques
cites work: Excluding infinite clique minors
cites work: A counter-example to ‘Wagner's conjecture’ for infinite graphs
cites work: Well-Quasi-Ordering Infinite Graphs with Forbidden Finite Planar Minor
cites work: Q3491608
DOI: 10.1006/JCTB.1998.1886
Recommended article: Excluding Subdivisions of Infinite Cliques
Recommended article: Excluding infinite clique minors
Recommended article: Cliques in graphs excluding a complete graph minor
Recommended article: Excluding a group-labelled graph
Recommended article: Counting sets with exceptions
Recommended article: Enumeration of isolated cliques and pseudo-cliques
Recommended article: Countable Amenable Identity Excluding Groups
Recommended article: Approximately counting cliques
Recommended article: Classes of graphs that exclude a tree and a clique and are not vertex Ramsey
Recommended article: Excluding subdivisions of bounded degree graphs
description: scientific article; zbMATH DE number 1346887