Forbidden subgraphs and bounds on the size of a maximum matching
Michael D. Plummer, Akira Saito · Journal of Graph Theory · 2005
Abstract Let K1,n denote the star on n + 1 vertices; that is, K1,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 K1,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 K1,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 K1,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 K1,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 K1,n, where n is bounded above by a certain function of α and k. © 2005 Wiley Periodicals, Inc. J Graph Theory