Graph structure theorem

Last updated

In mathematics, the graph structure theorem is a major result in the area of graph theory. The result establishes a deep and fundamental connection between the theory of graph minors and topological embeddings. The theorem is stated in the seventeenth of a series of 23 papers by Neil Robertson and Paul Seymour. Its proof is very long and involved. Kawarabayashi & Mohar (2007) and Lovász (2006) are surveys accessible to nonspecialists, describing the theorem and its consequences.

Contents

Setup and motivation for the theorem

A minor of a graph G is any graph H that is isomorphic to a graph that can be obtained from a subgraph of G by contracting some edges. If G does not have a graph H as a minor, then we say that G is H-free. Let H be a fixed graph. Intuitively, if G is a huge H-free graph, then there ought to be a "good reason" for this. The graph structure theorem provides such a "good reason" in the form of a rough description of the structure of G. In essence, every H-free graph G suffers from one of two structural deficiencies: either G is "too thin" to have H as a minor, or G can be (almost) topologically embedded on a surface that is too simple to embed H upon. The first reason applies if H is a planar graph, and both reasons apply if H is not planar. We first make precise these notions.

Tree width

The tree width of a graph G is a positive integer that specifies the "thinness" of G. For example, a connected graph G has tree width one if and only if it is a tree, and G has tree width two if and only if it is a series–parallel graph. Intuitively, a huge graph G has small tree width if and only if G takes the structure of a huge tree whose nodes and edges have been replaced by small graphs. We give a precise definition of tree width in the subsection regarding clique-sums. It is a theorem that if H is a minor of G, then the tree width of H is not greater than that of G. Therefore, one "good reason" for G to be H-free is that the tree width of G is not very large. The graph structure theorem implies that this reason always applies in case H is planar.

Corollary 1. For every planar graph H, there exists a positive integer k such that every H-free graph has tree width less than k.

It is unfortunate that the value of k in Corollary 1 is generally much larger than the tree width of H (a notable exception is when H = K4, the complete graph on four vertices, for which k = 3). This is one reason that the graph structure theorem is said to describe the "rough structure" of H-free graphs.

Surface embeddings

Roughly, a surface is a set of points with a local topological structure of a disc. Surfaces fall into two infinite families: the orientable surfaces include the sphere, the torus, the double torus and so on; the nonorientable surfaces include the real projective plane, the Klein bottle and so on. A graph embeds on a surface if the graph can be drawn on the surface as a set of points (vertices) and arcs (edges) that do not cross or touch each other, except where edges and vertices are incident or adjacent. A graph is planar if it embeds on the sphere. If a graph G embeds on a particular surface then every minor of G also embeds on that same surface. Therefore, a "good reason" for G to be H-free is that G embeds on a surface that H does not embed on.

When H is not planar, the graph structure theorem may be looked at as a vast generalization of the Kuratowski theorem. A version of this theorem proved by Wagner (1937) states that if a graph G is both K5-free and K3,3-free, then G is planar. This theorem provides a "good reason" for a graph G not to have K5 or K3,3 as minors; specifically, G embeds on the sphere, whereas neither K5 nor K3,3 embed on the sphere. Unfortunately, this notion of "good reason" is not sophisticated enough for the graph structure theorem. Two more notions are required: clique-sums and vortices.

Clique-sums

A clique in a graph G is any set of vertices that are pairwise adjacent in G. For a non-negative integer k, a k-clique-sum of two graphs G and K is any graph obtained by selecting a non-negative integer m ≤ k, selecting clique of size m in each of G and K, identifying the two cliques into a single clique of size m, then deleting zero or more of the edges that join vertices in the new clique.

If G1, G2, …, Gn is a list of graphs, then we may produce a new graph by joining the list of graphs via k-clique-sums. That is, we take a k-clique-sum of G1 and G2, then take a k-clique-sum of G3 with the resulting graph, and so on. A graph has tree width at most k if it can be obtained via k-clique-sums from a list of graphs, where each graph in the list has at most k + 1 vertices.

Corollary 1 indicates to us that k-clique-sums of small graphs describe the rough structure H-free graphs when H is planar. When H is nonplanar, we also need to consider k-clique-sums of a list of graphs, each of which is embedded on a surface. The following example with H = K5 illustrates this point. The graph K5 embeds on every surface except for the sphere. However there exist K5-free graphs that are far from planar. In particular, the 3-clique-sum of any list of planar graphs results in a K5-free graph. Wagner (1937) determined the precise structure of K5-free graphs, as part of a cluster of results known as Wagner's theorem:

Theorem 2. If G is K5-free, then G can be obtained via 3-clique-sums from a list of planar graphs, and copies of one special non-planar graph having 8-vertices.

We point out that Theorem 2 is an exact structure theorem since the precise structure of K5-free graphs is determined. Such results are rare within graph theory. The graph structure theorem is not precise in this sense because, for most graphs H, the structural description of H-free graphs includes some graphs that are notH-free.

Vortices (rough description)

One might be tempted to conjecture that an analog of Theorem 2 holds for graphs H other than K5. Perhaps it is true that: for any non-planar graph H, there exists a positive integer k such that every H-free graph can be obtained via k-clique-sums from a list of graphs, each of which either has at most k vertices or embeds on some surface that H does not embed on. Unfortunately, this statement is not yet sophisticated enough to be true. We must allow each embedded graph Gi to "cheat" in two limited ways. First, we must allow a bounded number of locations on the surface at which we may add some new vertices and edges that are permitted to cross each other in a manner of limited complexity. Such locations are called vortices. The "complexity" of a vortex is limited by a parameter called its depth, closely related to pathwidth. The reader may prefer to defer reading the following precise description of a vortex of depth k. Second, we must allow a limited number of new vertices to add to each of the embedded graphs with vortices.

Vortices (precise definition)

A face of an embedded graph is an open 2-cell in the surface that is disjoint from the graph, but whose boundary is the union of some of the edges of the embedded graph. Let F be a face of an embedded graph G and let v0, v1, ..., vn – 1, vn = v0 be the vertices lying on the boundary of F (in that circular order). A circular interval for F is a set of vertices of the form {va, va+1, …, va+s} where a and s are integers and where subscripts are reduced modulo n. Let Λ be a finite list of circular intervals for F. We construct a new graph as follows. For each circular interval L in Λ we add a new vertex vL that joins to zero or more of the vertices in L. Finally, for each pair {L, M} of intervals in Λ, we may add an edge joining vL to vM provided that L and M have nonempty intersection. The resulting graph is said to be obtained from G by adding a vortex of depth at most k(to the face F) provided that no vertex on the boundary of F appears in more than k of the intervals in Λ.

Statement of the graph structure theorem

Graph structure theorem.For any graph H, there exists a positive integer k such that every H-free graph can be obtained as follows:

  1. We start with a list of graphs, where each graph in the list is embedded on a surface on which H does not embed
  2. to each embedded graph in the list, we add at most k vortices, where each vortex has depth at most k
  3. to each resulting graph we add at most k new vertices (called apexes) and add any number of edges, each having at least one of its endpoints among the apexes.
  4. finally, we join via k-clique-sums the resulting list of graphs.

Note that steps 1. and 2. result in an empty graph if H is planar, but the bounded number of vertices added in step 3. makes the statement consistent with Corollary 1.

Refinements

Strengthened versions of the graph structure theorem are possible depending on the set H of forbidden minors. For instance, when one of the graphs in H is planar, then every H-minor-free graph has a tree decomposition of bounded width; equivalently, it can be represented as a clique-sum of graphs of constant size. [1] When one of the graphs in H can be drawn in the plane with only a single crossing, then the H-minor-free graphs admit a decomposition as a clique-sum of graphs of constant size and graphs of bounded genus, without vortices. [2] A different strengthening is also known when one of the graphs in H is an apex graph. [3]

See also

Notes

Related Research Articles

In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross each other. Such a drawing is called a plane graph or planar embedding of the graph. A plane graph can be defined as a planar graph with a mapping from every node to a point on a plane, and from every edge to a plane curve on that plane, such that the extreme points of each curve are the points mapped from its end nodes, and all curves are disjoint except on their extreme points.

In graph theory, the Robertson–Seymour theorem states that the undirected graphs, partially ordered by the graph minor relationship, form a well-quasi-ordering. Equivalently, every family of graphs that is closed under minors can be defined by a finite set of forbidden minors, in the same way that Wagner's theorem characterizes the planar graphs as being the graphs that do not have the complete graph K5 or the complete bipartite graph K3,3 as minors.

In graph theory, an undirected graph H is called a minor of the graph G if H can be formed from G by deleting edges, vertices and by contracting edges.

<span class="mw-page-title-main">Paul Seymour (mathematician)</span> British mathematician

Paul D. Seymour is a British mathematician known for his work in discrete mathematics, especially graph theory. He was responsible for important progress on regular matroids and totally unimodular matrices, the four colour theorem, linkless embeddings, graph minors and structure, the perfect graph conjecture, the Hadwiger conjecture, claw-free graphs, χ-boundedness, and the Erdős–Hajnal conjecture. Many of his recent papers are available from his website.

<span class="mw-page-title-main">Hadwiger conjecture (graph theory)</span> Unproven generalization of the four-color theorem

In graph theory, the Hadwiger conjecture states that if is loopless and has no minor then its chromatic number satisfies . It is known to be true for . The conjecture is a generalization of the four-color theorem and is considered to be one of the most important and challenging open problems in the field.

<span class="mw-page-title-main">Hadwiger number</span> Size of largest complete graph made by contracting edges of a given graph

In graph theory, the Hadwiger number of an undirected graph G is the size of the largest complete graph that can be obtained by contracting edges of G. Equivalently, the Hadwiger number h(G) is the largest number n for which the complete graph Kn is a minor of G, a smaller graph obtained from G by edge contractions and vertex and edge deletions. The Hadwiger number is also known as the contraction clique number of G or the homomorphism degree of G. It is named after Hugo Hadwiger, who introduced it in 1943 in conjunction with the Hadwiger conjecture, which states that the Hadwiger number is always at least as large as the chromatic number of G.

Colin de Verdière's invariant is a graph parameter for any graph G, introduced by Yves Colin de Verdière in 1990. It was motivated by the study of the maximum multiplicity of the second eigenvalue of certain Schrödinger operators.

<span class="mw-page-title-main">Wagner's theorem</span> On forbidden minors in planar graphs

In graph theory, Wagner's theorem is a mathematical forbidden graph characterization of planar graphs, named after Klaus Wagner, stating that a finite graph is planar if and only if its minors include neither K5 nor K3,3. This was one of the earliest results in the theory of graph minors and can be seen as a forerunner of the Robertson–Seymour theorem.

In graph theory, the treewidth of an undirected graph is an integer number which specifies, informally, how far the graph is from being a tree. The smallest treewidth is 1; the graphs with treewidth 1 are exactly the trees and the forests. The graphs with treewidth at most 2 are the series–parallel graphs. The maximal graphs with treewidth exactly k are called k-trees, and the graphs with treewidth at most k are called partial k-trees. Many other well-studied graph families also have bounded treewidth.

In graph theory, a path decomposition of a graph G is, informally, a representation of G as a "thickened" path graph, and the pathwidth of G is a number that measures how much the path was thickened to form G. More formally, a path-decomposition is a sequence of subsets of vertices of G such that the endpoints of each edge appear in one of the subsets and such that each vertex appears in a contiguous subsequence of the subsets, and the pathwidth is one less than the size of the largest set in such a decomposition. Pathwidth is also known as interval thickness, vertex separation number, or node searching number.

In graph theory, a branch of mathematics, many important families of graphs can be described by a finite set of individual graphs that do not belong to the family and further exclude all graphs from the family which contain any of these forbidden graphs as (induced) subgraph or minor.

The Journal of Combinatorial Theory, Series A and Series B, are mathematical journals specializing in combinatorics and related areas. They are published by Elsevier. Series A is concerned primarily with structures, designs, and applications of combinatorics. Series B is concerned primarily with graph and matroid theory. The two series are two of the leading journals in the field and are widely known as JCTA and JCTB.

<span class="mw-page-title-main">Branch-decomposition</span> Hierarchical clustering of graph edges

In graph theory, a branch-decomposition of an undirected graph G is a hierarchical clustering of the edges of G, represented by an unrooted binary tree T with the edges of G as its leaves. Removing any edge from T partitions the edges of G into two subgraphs, and the width of the decomposition is the maximum number of shared vertices of any pair of subgraphs formed in this way. The branchwidth of G is the minimum width of any branch-decomposition of G.

<span class="mw-page-title-main">Klaus Wagner</span>

Klaus Wagner was a German mathematician known for his contributions to graph theory.

<span class="mw-page-title-main">Clique-sum</span> Gluing graphs at complete subgraphs

In graph theory, a branch of mathematics, a clique sum is a way of combining two graphs by gluing them together at a clique, analogous to the connected sum operation in topology. If two graphs G and H each contain cliques of equal size, the clique-sum of G and H is formed from their disjoint union by identifying pairs of vertices in these two cliques to form a single shared clique, and then deleting all the clique edges or possibly deleting some of the clique edges. A k-clique-sum is a clique-sum in which both cliques have exactly k vertices. One may also form clique-sums and k-clique-sums of more than two graphs, by repeated application of the clique-sum operation.

<span class="mw-page-title-main">Apex graph</span> Graph which can be made planar by removing a single node

In graph theory, a branch of mathematics, an apex graph is a graph that can be made planar by the removal of a single vertex. The deleted vertex is called an apex of the graph. It is an apex, not the apex because an apex graph may have more than one apex; for example, in the minimal nonplanar graphs K5 or K3,3, every vertex is an apex. The apex graphs include graphs that are themselves planar, in which case again every vertex is an apex. The null graph is also counted as an apex graph even though it has no vertex to remove.

<span class="mw-page-title-main">Skew partition</span>

In graph theory, a skew partition of a graph is a partition of its vertices into two subsets, such that the induced subgraph formed by one of the two subsets is disconnected and the induced subgraph formed by the other subset is the complement of a disconnected graph. Skew partitions play an important role in the theory of perfect graphs.

In the mathematical theory of matroids, a minor of a matroid M is another matroid N that is obtained from M by a sequence of restriction and contraction operations. Matroid minors are closely related to graph minors, and the restriction and contraction operations by which they are formed correspond to edge deletion and edge contraction operations in graphs. The theory of matroid minors leads to structural decompositions of matroids, and characterizations of matroid families by forbidden minors, analogous to the corresponding theory in graphs.

<span class="mw-page-title-main">Planar cover</span>

In graph theory, a planar cover of a finite graph G is a finite covering graph of G that is itself a planar graph. Every graph that can be embedded into the projective plane has a planar cover; an unsolved conjecture of Seiya Negami states that these are the only graphs with planar covers.

<span class="mw-page-title-main">Kelmans–Seymour conjecture</span>

In graph theory, the Kelmans–Seymour conjecture states that every 5-vertex-connected graph that is not planar contains a subdivision of the 5-vertex complete graph K5. It is named for Paul Seymour and Alexander Kelmans, who independently described the conjecture; Seymour in 1977 and Kelmans in 1979. A proof was announced in 2016, and published in four papers in 2020.

References

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.