Forbidden subgraphs and bounds on the size of a maximum matching

✍ Scribed by Michael D. Plummer; Akira Saito

• Publisher: John Wiley and Sons
• Year: 2005
• Tongue: English
• Weight: 126 KB
• Volume: 50
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.20087

✦ Synopsis

Abstract

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