A Relationship Between Minors and Linkages

Abstract

Linkage is very important in Very Large Scale Integration (VLSI) physical design. In this paper, we mainly study the relationship between minors and linkages. Thomassen conjectured that every $(2k+2)$-connected graph is $k$-linked. For $k\ge 4$, $K_{3k-1}$ with $k$ disjoint edges deleted is a counterexample to this conjecture, however, it is still open for $k=3$. Thomas and Wollan proved that every $6$-connected graph on $n$ vertices with $5n–14$ edges is $3$-linked. Hence they obtain that every $10$-connected graph is $3$-linked. Chen et al. showed that every $6$-connected graph with $K_9^{-}$ as a minor is $3$-linked, and every $7$-connected graph with $K_9^{-}$ as a minor is $(2,2k-1)$-linked. Using a similar method, we prove that every $8$-connected graph with $K_{2k+3}^{-}$ as a minor is $4$-linked, and every $(2k+1)$-connected graph with $K_{2k+3}^{-}$ as a minor is $(2,2k–1)$-linked. Our results extend Chen et al.’s conclusions, improve Thomas and Wollan’s results, and moreover, they give a class of graphs that satisfy Thomassen’s conjecture for $k=4$.