A pair of forbidden subgraphs and perfect matchings in graphs of high connectivity (Q2428638)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 6028298
Language Label Description Also known as
default for all languages
No label defined
    English
    A pair of forbidden subgraphs and perfect matchings in graphs of high connectivity
    scientific article; zbMATH DE number 6028298

      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