Unavoidable Cycle-Contraction Minors of Large 2-Connected Graphs
Abstract
Abstract. It is well known that every sufficiently large connected graph has, as an induced subgraph, [Formula: see text], [Formula: see text], or an [Formula: see text]-vertex path. A 2023 paper of Allred, Ding, and Oporowski identified a set of unavoidable induced subgraphs of sufficiently large 2-connected graphs. In this paper, we establish a dual version of this theorem by focusing on the minors obtained by contracting cycles.
Fields of Study & Subjects
Advanced Graph Theory Research
Interconnection Networks and Systems
Complexity and Algorithms in Graphs
Publication details
- Journal / source
- SIAM Journal on Discrete Mathematics
- Volume
- 40
- Issue
- 2
- Pages
- 612–632
- Publication date
- 27 April 2026
- Language
- EN