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
    0 references
    0 references
    0 references
    0 references
    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

    Identifiers