A Ramsey-type theorem on deficiency

Ramsey's Theorem states that a graph G has bounded order if and only if G contains no complete graph Kₙ or empty graph Eₙ as its induced subgraph. The Gy\'arf\'as-Sumner conjecture says that a graph G has bounded chromatic number if and only if it contains no induced subgraph isomorphic to Kₙ or a tree T. 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, i. e. , we characterize all the forbidden induced subgraphs for graphs G with bounded deficiency. As an application, we answer a question proposed by Fujita, Kawarabayashi, Lucchesi, Ota, Plummer and Saito (JCTB, 2006).