Unavoidable Induced Subgraphs of Large 2-Connected Graphs

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.

15 pages

Cited by in corpus (1)

• Unavoidable Induced Subgraph of Infinite 2-connected Graphs