caa a22 4500 445358513 CHVBK 20180317142908.0 cr unu---uuuuu 170323e20111201xx s 000 0 eng 10.1007/s00493-011-2655-y doi (NATIONALLICENCE)springer-10.1007/s00493-011-2655-y A pair of forbidden subgraphs and perfect matchings in graphs of high connectivity [Elektronische Daten] [Jun Fujisawa, Shinya Fujita, Michael Plummer, Akira Saito, Ingo Schiermeyer] Sumner [7] 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 ≥ 2, every m-connected K 1,m+1-free graph of even order has a perfect matching. In [6], two of the present authors obtained a converse of sorts to Sumner's result by asking what 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 [2], 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 paper, we give an answer to this problem. Together with the result in [2], a complete characterization of the pairs is given. János Bolyai Mathematical Society and Springer Verlag, 2011 Fujisawa Jun Faculty of Business and Commerce, Keio University, Hiyoshi 4-1-1, Kohoku-Ku, 223-8521, Yokohama, Kanagawa, Japan aut Fujita Shinya Department of Mathematics, Gunma National College of Technology, 580 Toriba, 371-8530, Maebashi, Gunma, Japan aut Plummer Michael Department of Mathematics, Vanderbilt University, 37240, Nashville, Tennessee, USA aut Saito Akira Department of Computer Science, Nihon University, Sakurajosui 3-25-40, 156-8550, Setagaya-Ku, Tokyo, Japan aut Schiermeyer Ingo Institut für Diskrete Mathematik und Algebra, TU Bergakademie Freiberg, 09596, Freiberg, Germany aut Combinatorica Springer-Verlag 31/6(2011-12-01), 703-723 0209-9683 31:6<703 2011 31 493 https://doi.org/10.1007/s00493-011-2655-y text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00493-011-2655-y text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Fujisawa Jun Faculty of Business and Commerce, Keio University, Hiyoshi 4-1-1, Kohoku-Ku, 223-8521, Yokohama, Kanagawa, Japan aut NATIONALLICENCE 700 1- Fujita Shinya Department of Mathematics, Gunma National College of Technology, 580 Toriba, 371-8530, Maebashi, Gunma, Japan aut NATIONALLICENCE 700 1- Plummer Michael Department of Mathematics, Vanderbilt University, 37240, Nashville, Tennessee, USA aut NATIONALLICENCE 700 1- Saito Akira Department of Computer Science, Nihon University, Sakurajosui 3-25-40, 156-8550, Setagaya-Ku, Tokyo, Japan aut NATIONALLICENCE 700 1- Schiermeyer Ingo Institut für Diskrete Mathematik und Algebra, TU Bergakademie Freiberg, 09596, Freiberg, Germany aut NATIONALLICENCE 773 0- Combinatorica Springer-Verlag 31/6(2011-12-01), 703-723 0209-9683 31:6<703 2011 31 493 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer