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:
- 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.
- 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.
- 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.
- 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