A pair of forbidden subgraphs and perfect matchings in graphs of high connectivity (Q2428638)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A pair of forbidden subgraphs and perfect matchings in graphs of high connectivity |
scientific article |
Statements
A pair of forbidden subgraphs and perfect matchings in graphs of high connectivity (English)
0 references
26 April 2012
0 references
\textit{D.~Sumner} [J. Lond. Math. Soc., II. Ser. 13, 351--359 (1976; Zbl 0338.05118)] proved that every connected \(K_{1,3}\)-free graph of even order has a perfect matching, He also considered graphs of higher connectivity and proved that if \(m\geq 2\), every \(m\)-connected \(K_{1,m+1}\)-free graph of even order has a perfect matching. In [\textit{M. D.~Plummer an A.~Saito}, J. Graph Theory 50, 1--12 (2005; Zbl 1070.05070)] a converse of sorts to Sumner's result was obtained by asking which single graph one can forbid to force the existence of a perfect matching in an \(m\)-connected graph of even order and proved that a star is the only possibility. In [J. Comb. Theory, Ser. B 96, 315--324 (2006; Zbl 1090.05057)], \textit{S.~Fujita et al.} extended this work by considering pairs of forbidden subgraphs which force the existence of a perfect matching in a connected graph of even order, but they did not settle the same problem for graphs of higher connectivity. In this work an answer to this problem is given and, together with the result in [\textit{S.~Fujita et al.}, J. Comb. Theory, Ser. B 96, 315--324 (2006; Zbl 1090.05057)], a complete characterization of the pairs is obtained.
0 references
graphs of high connectivity
0 references
perfect matching
0 references
forbidden subgraphs
0 references