Forbidden subgraphs and bounds on the size of a maximum matching

Let K 1, n denote the star on n  + 1 vertices; that is, K 1, n is the complete bipartite graph having one vertex in the first vertex class of its bipartition and n in the second. The special graph K 1,3 , called the claw , has received much attention in the literature. In particular, a graph G is said to be claw‐free if G possesses no K 1,3 as an induced subgraph. A well‐known theorem of Sumner and, independently, Las Vergnas says that every connected even claw‐free graph contains a perfect matching. (Later, Jünger, Pulleyblank, and Reinelt proved that if G is connected, claw‐free, and odd, then G must contain a near‐perfect matching.) More generally, Sumner proved that if G is K 1, n ‐free, ( n  − 1)‐connected, and even, then G must contain a perfect matching. In this paper, we extend these results in several ways. First, we show that if G is a k ‐connected K 1, n ‐free graph on p vertices, then def( G ) is bounded above by a certain function of k , n , and p , where def( G ) is the deficiency of G . (The deficiency of a graph measures how far a maximum matching is from being perfect; that is, def ( G ) =  p  − 2ν( G ), where ν( G ) is the size of any maximum matching in G .) We then provide examples to show that this upper bound is sharp for each value of k and n . We then prove a result that is a type of converse to the above theorem in the following sense. Suppose that H is a connected graph and suppose that there exist constants α and β, 0 ≤ α < 1, such that every k ‐connected H ‐free graph G of sufficiently large order satisfies ( G ) ≤ α| V ( G )| + β. Then the excluded subgraph H must be a K 1, n , where n is bounded above by a certain function of α and k . © 2005 Wiley Periodicals, Inc. J Graph Theory