Unavoidable induced subgraphs forced by graphs with many vertices of prescribed properties

Abstract

Given a function $p:V(G)\to \mathbb{N}$ and an integer $k\ge 0$, define $p_k(G)$ as the number of vertices with $p(v)\ge k$. We say that $p_k(G)$ is bounded for all $\HH$-free graphs if there exists a constant $c=c(\HH)$ such that $p_k(G)<c$ for all such graphs $G$. Here, a graph $G$ is said to be $\HH$-free if it contains no member of $\HH$ as an induced subgraph. When $p$ represents the degree of a vertex, Ramsey's theorem implies that $p_0(G)$ is bounded for every $\{K_n,E_n\}$-free graphs, where $K_n$ and $E_n$ denote the complete graph and the edgeless graph on $n$ vertices, respectively. The connected version of Ramsey's theorem says that $p_0(G)$ is bounded for all $\{K_n,P_n,K_{1,n}\}$-free connected graphs, where $P_n$ and $K_{1,n}$ are the $n$-vertex path and the star with $n$ leaves. In this paper, we extend the Ramsey's theorem to $p_2(G)$ where $p$ denotes the degree, the local independent number, the local component number, and sharp degree, that is, we characterize the forbidden family of graphs $\HH$ such that $p_2(G)$ is bounded for all (connected) $\HH$-free graphs. Moreover, we also characterize the forbidden family of graphs $\HH$ for which there is a constant $c=c(\HH)$ such that $p_c(G)$ is bounded for all $\HH$-free graphs.

16 pages, 1 figure