Title: A Ramsey-type theorem on deficiency Show Chinese title

Title: 关于缺陷的Ramsey型定理

Abstract: Ramsey's Theorem states that a graph $G$ has bounded order if and only if $G$ contains no complete graph $K_n$ or empty graph $E_n$ 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_n$ 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). Show Chinese abstract

Abstract: 拉姆齐定理指出，图 $G$的阶数有界当且仅当 $G$不包含完全图 $K_n$或空图 $E_n$作为其导出子图。 吉亚尔法斯-桑纳猜想指出，图 $G$的色数有界当且仅当它不包含与 $K_n$或树 $T$同构的导出子图。 图的亏缺是指不能被最大匹配覆盖的顶点数量。 在本文中，我们证明了一个关于缺陷的Ramsey型定理，即我们刻画了所有禁止的诱导子图，这些子图属于具有有界缺陷的图$G$。 作为应用，我们回答了Fujita、Kawarabayashi、Lucchesi、Ota、Plummer和Saito（JCTB，2006）提出的一个问题。