A Ramsey‐Type Theorem on Deficiency

ABSTRACT The Ramsey Theorem says that a graph has bounded order if and only if contains no complete graph or empty graph as its induced subgraph. The Gyárfás‐Sumner conjecture states that a graph has bounded chromatic number if and only if it contains no induced subgraph isomorphic to or a tree . The deficiency of a graph is the number of vertices that cannot be covered by a maximum matching. In this paper, we prove a Ramsey‐type theorem for deficiency, that is, we characterize all the forbidden induced subgraphs for graphs with bounded deficiency. In this application, we answer a question proposed by Fujita et al. (2006).