In absence of long chordless cycles, large tree-width becomes a local phenomenon
From MaRDI portal
Publication:2338644
DOI10.1016/j.jctb.2019.04.004zbMath1428.05122arXiv1803.02703OpenAlexW2964102969MaRDI QIDQ2338644
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
Trees (05C05) Paths and cycles (05C38) Coloring of graphs and hypergraphs (05C15) Distance in graphs (05C12)
Related Items (7)
Tree-width dichotomy ⋮ Degeneracy of \(P_t\)-free and \(C_{\geq t}\)-free graphs with no large complete bipartite subgraphs ⋮ 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 ⋮ Packing and Covering Induced Subdivisions ⋮ Dense Induced Subgraphs of Dense Bipartite Graphs ⋮ Treewidth versus Clique Number. I. Graph Classes with a Forbidden Structure
Cites Work
- Unnamed Item
- Unnamed Item
- Induced subdivisions in \(K_{s,s}\)-free graphs of large average degree
- Induced subgraphs of graphs with large chromatic number. III: Long holes
- Tree-chromatic number
- Graph minors. V. Excluding a planar graph
- Treewidth for graphs with small chordality
- A tight Erdős-Pósa function for long cycles
- Recent techniques and results on the Erdős-Pósa property
- The Erdős-Pósa property for long circuits
- Graph Theory
- k-Chordal Graphs: From Cops and Robber to Compact Routing via Treewidth
- Graph Theory and Probability
- On the presence of disjoint subgraphs of a specified type
- Erd\H{o}s-P\'osa property of chordless cycles and its applications
- On the Block Number of Graphs
- On Independent Circuits Contained in a Graph
- On a problem of K. Zarankiewicz
This page was built for publication: In absence of long chordless cycles, large tree-width becomes a local phenomenon
