In absence of long chordless cycles, large tree-width becomes a local phenomenon

2018/03/07 by Weißauer, Daniel
#05C83 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1803.02703

Abstract

We prove that, for all ℓ and s, every graph of sufficiently large tree-width contains either a complete bipartite graph K_s,s or a chordless cycle of length greater than ℓ.

Related

• Chordal graphs, even-hole-free graphs and sparse obstructions to bounded treewidth
• Chords of longest cycles in graphs with large circumferences
• Graphs with bounded tree-width and large odd-girth are almost bipartite
• Sparse Induced Subgraphs of Large Treewidth
• Algebraically grid-like graphs have large tree-width