A pair of forbidden subgraphs and perfect matchings

作者：Fujita S^*; Kawarabayashi K; Lucchesi CL; Ota K; Plummer MD; Saito A

来源：Journal of Combinatorial Theory - Series B, 2006, 96(3): 315-324.

DOI：10.1016/j.jctb.2005.08.002

• perfect matching
• near-perfect matching
• forbidden subgraph

In this paper, we study the relationship between forbidden subgraphs and the existence of a matching. Let W be a set of connected graphs. each of which has three or more vertices. A graph G is said to be H-free if no graph in W is ail induced subgraph of G. We completely characterize the set H such that every connected H-free graph of sufficiently large even order has a perfect matching in the following cases.
(1) Every graph in R is triangle-free.
(2) H consists of two graphs (i.e. a pair of forbidden subgraphs).
A matching M in a graph of odd order is said to be a near-perfect matching if every vertex of G but one is incident with an edge of M. We also characterize H such that every H-free graph of sufficiently large odd order has a near-perfect matching in the above cases.

• 出版日期2006-5