Linkages in Large Graphs of Bounded Tree-Width

2014/02/22 by Jan-Oliver Fröhlich, Ken-ichi Kawarabayashi, Fröhlich, Jan-Oliver +8
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Interconnection Networks and Systems #acm:05C38 #acm:05C40 #acm:05C57 #acm:05C83 #math.CO #msc:05C38 #msc:05C40 #msc:05C57 #msc:05C83

paper · pdf · doi:10.48550/arxiv.1402.5549

68 pages, 1 figure

arxiv created 2014/02/22 · arxiv updated 2014/02/25

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.

Related

• Highly linked tournaments
• Linkages in Polytope Graphs
• Edge-disjoint linkage in infinite graphs
• Induced subgraphs and tree decompositions V. Small components of big vertices
• A Proof of the Barát-Thomassen Conjecture