Linkages in Large Graphs of Bounded Tree-Width

Jan-Oliver Fröhlich, Ken‐ichi Kawarabayashi, Theodor Müller, Julian Pott, Paul WollanarXiv 2014 · DOI · arXiv

Title: Linkages in Large Graphs of Bounded Tree-Width
Abstract: We show that all sufficiently large (2k+3)-connected graphs of bounded tree-width are k-linked. Thomassen has conjectured that all sufficiently large (2k+2)-connected graphs are k-linked.

Introduction

In the study of graph theory, understanding the relationship between connectivity and linkage is a fundamental challenge. While $k$-connectivity ensures that a graph remains in one piece after the removal of any $k-1$ vertices, $k$-linkage is a significantly more stringent requirement. A graph is $k$-linked if, for any $2k$ distinct vertices paired into $k$ sets, there exist $k$ vertex-disjoint paths connecting each pair.

While it is well-established that every $k$-linked graph must be $k$-connected, the inverse—determining how much connectivity is required to guarantee a graph is $k$-linked—has been a subject of intense research for decades. Early bounds were as high as $22k$, and while the current general bound stands at $10k$, Carsten Thomassen conjectured in 1980 that for "sufficiently large" graphs, $(2k + 2)$-connectivity should be sufficient. This paper makes significant progress toward this conjecture by proving it for the class of graphs with bounded tree-width.

Structural Foundations: Bounded Tree-Width

The authors focus on graphs with bounded tree-width—structures that, while potentially large, maintain a tree-like decomposition. This restriction is powerful because it allows for the use of path decompositions. In very large graphs of this type, the absence of a dense clique minor forces the graph into a regular, elongated structure.

By exploiting this "large graph advantage," the researchers can decompose the graph into a sequence of "bags" and establish a "foundational linkage"—a set of paths that traverse the length of the decomposition. The proof then hinges on whether these paths can be rerouted to connect specific target pairs.

Methodology: From Topology to Token Games

The paper employs a sophisticated blend of structural graph theory and combinatorial puzzles to bridge the gap between connectivity and linkage:

  1. Stable Regular Decompositions: The authors refine path decompositions until they are "stable." In a stable decomposition, the foundational linkage is robust; no simple rerouting of paths can create new connections between them, providing a predictable environment for path manipulation.
  2. The Token Game: The topological problem of finding disjoint paths is translated into a discrete puzzle. The authors imagine "tokens" on an auxiliary graph $H$, where moving a token represents rerouting a path through a "bridge" in the original graph. To solve this, they utilize Richard Wilson’s 1974 theorem regarding the reachability of permutations in graphs (similar to the logic of the 15-puzzle). If the token game can be "won," the required linkage exists.
  3. Rural Societies: For instances where the graph exhibits planar-like characteristics, the authors apply the "Rural Societies" framework developed by Robertson and Seymour. This ensures that necessary path intersections (crosses) exist unless the graph's structure is extremely restricted.
  4. Bipartite Subdivisions: A critical technical lemma (Lemma 7.1) shows that if a $2k$-connected graph contains a sufficiently large subdivision of a complete bipartite graph ($TK_{2k,2k}$), it is inherently $k$-linked. This provides a fallback mechanism when the token game approach is not directly applicable.

Key Results

The primary contribution of this work is Theorem 1.1: For any integers $k$ and $w$, there exists a size $N$ such that every $(2k + 3)$-connected graph with tree-width less than $w$ and at least $N$ vertices is $k$-linked.

This result brings the mathematical community within a single vertex of Thomassen’s $(2k+2)$ conjecture for this broad class of graphs. Furthermore, the paper refines the methodology for handling stable decompositions in large graphs, offering a robust toolkit for future problems in graph minor theory.

Discussion and Limitations

Despite the strength of the $(2k+3)$ result, the $+1$ gap remains an area of interest. The authors identify that the proof's current limitations at $(2k+2)$ stem from the "richness" requirements of the token game. Specifically, the connectivity must be high enough to ensure the auxiliary graph $H$ has the necessary properties to support the required permutations.

Additionally, while bounded tree-width covers a vast array of graphs, it is a structural constraint. While other researchers have suggested methodologies to extend these bounds to all large graphs by examining planar-like patches, this paper provides a rigorous, self-contained proof for the tree-width-constrained case. Finally, it is noted that the constant $N$ (the required number of vertices) is likely extremely large due to the reliance on Ramsey-type arguments, making this a result of structural existence rather than one of immediate algorithmic utility for small graphs.

Summary updated

Abstract

We show that all sufficiently large (2k+3)-connected graphs of bounded tree-width are k-linked. Thomassen has conjectured that all sufficiently large (2k+2)-connected graphs are k-linked.
BibTeX
@misc{frohlich2014linkages,
  author = {Jan-Oliver Fröhlich and Ken‐ichi Kawarabayashi and Theodor Müller and Julian Pott and Paul Wollan},
  title = {{Linkages in Large Graphs of Bounded Tree-Width}},
  year = {2014},
  eprint = {1402.5549},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1402.5549},
}
Figure