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).
This work presents a significant advancement in extremal graph theory by providing a Ramsey-type theorem for the graph parameter known as deficiency. Deficiency, defined as def(G) = |V(G)| - 2ν(G) (where ν(G) is the size of a maximum matching), quantifies the number of vertices not covered by a maximum matching in a graph G. The paper precisely characterizes all finite families of forbidden induced subgraphs whose absence guarantees a bounded deficiency for connected graphs.
The significance of this result lies in its extension of classical Ramsey theory to a fundamental graph parameter related to matching. Historically, Ramsey’s Theorem characterized graphs with bounded order by forbidding complete graphs (\(K_n\)) or empty graphs (\(E_n\)) as induced subgraphs. Subsequent research, exemplified by the Gyárfás-Sumner conjecture concerning chromatic number (which bounds chromatic number by forbidding complete graphs and trees), has sought to apply this “forbidden induced subgraph” paradigm to other graph invariants. This paper places deficiency squarely within this framework, offering a complete structural characterization. Furthermore, as an important application of their main theorem, the authors provide an answer to a specific open question posed by Fujita, Kawarabayashi, Lucchesi, Ota, Plummer, and Saito (2006) regarding minimal forbidden sets for graphs with a deficiency bounded by a specific integer d.
The key innovation of this research is the explicit identification of the finite family of induced subgraphs that, if absent from a connected graph, guarantee its deficiency is bounded. This comprehensive characterization, detailed in Theorem 1.6, involves a collection of specially constructed graph families, including various stars (\(K_{1,n}\)), specific branched paths (\(T_n\)), complete bipartite graphs with attached paths (\(K_{h,p}\)), and other intricately designed structures (\(F_1, F_2, F_3, F_4, F_R\)). The non-triviality of this result stems from the global nature of deficiency, which makes local forbidden subgraph conditions challenging to establish. The proof methodology demonstrates innovative applications of structural decomposition techniques, particularly a “level-by-level” analysis of graphs based on distance from a central vertex, combined with careful construction of maximum matchings within these decompositions. The “only if” part of the theorem relies on devising these complex graph families that can exhibit arbitrarily large deficiency without containing any of the proposed forbidden structures.
The main prior ingredients for this work draw heavily from several established areas of graph theory:
1. Classical Ramsey Theory: The foundational concept that a graph property can be characterized by a finite set of forbidden induced subgraphs. The general framework b-B-µ (characterizing graphs G where a parameter µ(G) is bounded for H-free graphs) is a direct generalization of Ramsey’s original problem.
2. Graph Matching Theory: The very definition of deficiency is rooted in the concept of maximum matchings. Prior results on matching, such as those related to factor-critical graphs or graphs admitting perfect matchings, are implicitly or explicitly used. Notably, the paper references Theorem 1.5 by Las Vergnas, Sumner, Jünger, Pulleyblank, and Reinelt, which states that every connected claw-free graph has deficiency at most one. This result highlights the significance of the claw (\(K_{1,3}\)) as a fundamental forbidden subgraph for low deficiency and provides a baseline for the broader characterization.
3. Structural Graph Theory and Decomposition: The “if” part of the proof (showing that H-free graphs have bounded deficiency) likely employs sophisticated structural arguments. This includes graph decomposition techniques, often involving partitioning vertices based on distance or other properties, and then analyzing matching properties within these partitions. The use of bipartite graph properties, such as those related to induced matchings (Lemma 2.4), is also crucial in these structural arguments.
4. Extremal Graph Theory: The broader field of extremal graph theory, which seeks to find the maximum or minimum possible order of a graph under certain structural constraints, provides the context and motivation for identifying such forbidden substructures. Problems like the Gyárfás-Sumner conjecture serve as direct inspiration for applying similar characterization efforts to other graph parameters.