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

DOI10.1016/J.JCTB.2019.04.004MaRDI QIDQ2338644zbMATH OpenOpenAlexFDO

Authors Daniel Weißauer

Publication date 21 November 2019

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1803.02703

zbMATH Keywords

\(\ell\)-chordal graphs\(k\)-blocksinduced cyclesobstructiontree-decompositionstree-width

Mathematics Subject Classification ID

Trees (05C05) Distance in graphs (05C12) Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38)

Abstract: We prove that, for all $ell$ 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 $ell$.

Recommendations

• scientific article; zbMATH DE number 1696534
• Graphs with bounded tree-width and large odd-girth are almost bipartite
• Transversals of longest cycles in chordal and bounded tree-width graphs
• Algebraically grid-like graphs have large tree-width
• scientific article; zbMATH DE number 4164908

Cites work

• \(k\)-chordal graphs: from cops and robber to compact routing via treewidth
• A tight Erdős-Pósa function for long cycles
• Erdős-Pósa property of chordless cycles and its applications
• Graph minors. V. Excluding a planar graph
• Graph theory
• Graph Theory and Probability
• scientific article; zbMATH DE number 1941338 (Why is no real title available?)
• scientific article; zbMATH DE number 4183452 (Why is no real title available?)
• Induced subdivisions in \(K_{s,s}\)-free graphs of large average degree
• Induced subgraphs of graphs with large chromatic number. III: Long holes
• On a problem of K. Zarankiewicz
• On Independent Circuits Contained in a Graph
• On the block number of graphs
• On the presence of disjoint subgraphs of a specified type
• Recent techniques and results on the Erdős-Pósa property
• The Erdős-Pósa property for long circuits
• Tree-chromatic number
• Treewidth for graphs with small chordality

Cited in

(12)

• Tree-width dichotomy
• Degeneracy of \(P_t\)-free and \(C_{\geq t}\)-free graphs with no large complete bipartite subgraphs
• Packing and covering induced subdivisions
• Dense Induced Subgraphs of Dense Bipartite Graphs
• Treewidth versus clique number. I: Graph classes with a forbidden structure
• Graphs with bounded tree-width and large odd-girth are almost bipartite
• Towards a conjecture of Birmelé–Bondy–Reed on the Erdős–Pósa property of long cycles
• Induced subgraphs and tree decompositions. VII: Basic obstructions in \(H\)-free graphs
• Tree independence number. I. (Even hole, diamond, pyramid)-free graphs
• A survey of degree-boundedness
• Sparse induced subgraphs of large treewidth
• Complexity framework for forbidden subgraphs. I: The framework

This page was built for publication: In absence of long chordless cycles, large tree-width becomes a local phenomenon

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2338644)