Unavoidable Induced Subgraphs of Large 2-Connected Graphs

DOI10.1137/21M1447593MaRDI QIDQ6098457zbMATH OpenOpenAlexFDO

Authors Sarah R. Allred, Guoli Ding, Bogdan Oporowski

Publication date 14 June 2023

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

2-connected graphsRamsey theoremunavoidable induced subgraphs

Mathematics Subject Classification ID

Generalized Ramsey theory (05C55) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Structural characterization of families of graphs (05C75)

Abstract: Ramsey proved that for every positive integer $n$, every sufficiently large graph contains an induced $K_n$ or $overline{K}_n$. Among the many extensions of Ramsey's Theorem there is an analogue for connected graphs: for every positive integer $n$, every sufficiently large connected graph contains an induced $K_n$, $K_{1,n}$, or $P_n$. In this paper, we establish an analogue for 2-connected graphs. In particular, we prove that for every integer exceeding two, every sufficiently large 2-connected graph contains one of the following as an induced subgraph: $K_n$, a subdivision of $K_{2,n}$, a subdivision of $K_{2,n}$ with an edge between the two vertices of degree $n$, and a well-defined structure similar to a ladder.

Recommendations

• Subdivisions of large complete bipartite graphs and long induced paths in k‐connected graphs
• Highly connected subgraphs of graphs with given independence number
• Unavoidable doubly connected large graphs
• Large Induced Subgraphs with All Degrees Odd
• Isolating highly connected induced subgraphs

Cites work

• A Ramsey-type theorem for traceable graphs
• scientific article; zbMATH DE number 830463 (Why is no real title available?)
• scientific article; zbMATH DE number 3365295 (Why is no real title available?)
• Typical subgraphs of 3- and 4-connected graphs
• Unavoidable minors of large 3-connected binary matroids
• Unavoidable minors of large 3-connected matroids
• Unavoidable parallel minors of 4-connected graphs

Cited in

(5)

• Unavoidable doubly connected large graphs
• Unavoidable induced subgraphs in large graphs with no homogeneous sets
• scientific article; zbMATH DE number 125483 (Why is no real title available?)
• Unavoidable induced subgraphs of infinite 2-connected graphs
• Unavoidable cycle-contraction minors of large 2-connected graphs

This page was built for publication: Unavoidable Induced Subgraphs of Large 2-Connected Graphs

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