Induced subgraphs of graphs with large deficiency

The deficiency of a graph G, denoted by (G), is the number of vertices not saturated by a maximum matching. A bone Bᵢ is the tree obtained by attaching two pendent edges to each of the end vertices of a path Pᵢ. The local independence number of G, denoted by αₗ(G), is defines as the maximum integer t such that G contains an induced star K1,t. Motivated by the seminal works of Scott and Seymour~(2016), Chudnovsky et al. (2017, 2020) on finding special types of holes in graphs with large chromatic number and bounded clique number, we establish an analog result by finding special types of bones in graphs with large deficiency and bounded local independence number. Fujita et al. (2006) proved that (G)≤ n-2 if G is a connected graph with αₗ(G)<n and containing no bones. We further establish exact extremal deficiency bounds for connected graphs with bounded local independence number that exclude specific bone configurations. An algorithm that constructs large matchings and establishes an upper bound on the deficiency is also provided.