Forbidden induced subgraphs for perfect matchings. (English) Zbl 1263.05078

Ota, Katsuhiro; Sueiro, Gabriel

Graphs Comb. 29, No. 2, 289-299 (2013).

Summary: Let \({\mathcal{F}}\) be a family of connected graphs. A graph \(G\) is said to be \({\mathcal{F}}\)-free if \(G\) is \(H\)-free for every graph \(H\) in \({\mathcal{F}}\). We study the problem of characterizing the families of graphs \({\mathcal{F}}\) such that every large enough connected \({\mathcal{F}}\)-free graph of even order has a perfect matching.
This problems was previously studied in M. D. Plummer and A. Saito [J. Graph Theory 50, No. 1, 1–12 (2005; Zbl 1070.05070)], S. Fujita et al. [J. Comb. Theory, Ser. B 96, No. 3, 315–324 (2006; Zbl 1090.05057)] and K. Ota et al. [J. Graph Theory 67, No. 3, 250–259 (2011; Zbl 1225.05203)], where the authors were able to characterize such graph families \({\mathcal{F}}\) restricted to the cases \({|\mathcal{F}|\leq 1, |\mathcal{F}| \leq 2}\) and \({|\mathcal{F}| \leq 3}\), respectively.
In this paper, we complete the characterization of all the families that satisfy the above mentioned property. Additionally, we show the families that one gets when adding the condition \({|\mathcal{F}| \leq k}\) for some \(k \geq 4\).

MSC:

05C70	Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C60	Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)

Keywords:

perfect matching; forbidden subgraph

Citations:

Zbl 1070.05070; Zbl 1090.05057; Zbl 1225.05203

References:

[1]	Chartrand G., Lesniak L.: Graphs & Digraphs, 3rd edn. Wadsworth & Brooks/Coles, Monterey (1996) · Zbl 0890.05001
[2]	Fujisawa J., Ota K., Ozeki K., Sueiro G.: Forbidden induced subgraphs for star-free graphs. Discrete Math. 311(21), 2475–2484 (2011) · Zbl 1238.05144 · doi:10.1016/j.disc.2011.07.022
[3]	Fujita S., Kawarabayashi K., Lucchesi C.L., Ota K., Plummer M.D., Saito A.: A pair of forbidden subgraphs and perfect matchings. J. Combin. Theory Ser. B 96(3), 315–324 (2006) · Zbl 1090.05057 · doi:10.1016/j.jctb.2005.08.002
[4]	Las Vergnas M.: A note on matchings in graphs. Cahiers Centre Études Recherche Opér 17, 257–260 (1975) · Zbl 0315.05123
[5]	Ota, K., Ozeki, K., Sueiro, G.: Forbidden induced subgraphs for near perfect matchings (submitted) · Zbl 1277.05140
[6]	Ota K., Plummer M.D., Saito A.: Forbidden triples for perfect matchings. J. Graph Theory 67(3), 250–259 (2011) · Zbl 1225.05203 · doi:10.1002/jgt.20529
[7]	Plummer M.D., Saito A.: Forbidden subgraphs and bounds on the size of a maximum matching. J. Graph Theory 50(1), 1–12 (2005) · Zbl 1070.05070 · doi:10.1002/jgt.20087
[8]	Sumner D.P.: 1-factors and antifactor sets. J. Lond. Math. Soc. s2–13(2), 351–359 (1976) · Zbl 0338.05118 · doi:10.1112/jlms/s2-13.2.351
[9]	Tutte W.T.: The factorization of linear graphs. J. Lond. Math. Soc. s1–22(2), 107–111 (1947) · Zbl 0029.23301 · doi:10.1112/jlms/s1-22.2.107