On the matching extendability of graphs in surfaces

Journal of Combinatorial Theory, Series B - Tập 98 - Trang 105-115 - 2008
R.E.L. Aldred1, Ken-ichi Kawarabayashi2, Michael D. Plummer3
1Department of Mathematics, Otago University, PO Box 56, Dunedin, New Zealand
2National Institute of Informatics, 2-1-2 Hitotsubashi, Chiyoda-ku, Tokyo 101-8430, Japan
3Department of Mathematics, Vanderbilt University, Nashville, TN 37240, USA

Tài liệu tham khảo

Dean, 1992, The matching extendability of surfaces, J. Combin. Theory Ser. B, 54, 133, 10.1016/0095-8956(92)90071-5 Győri, 1992, The Cartesian product of a k-extendable and an ℓ-extendable graph is (k+ℓ+1)-extendable, Discrete Math., 101, 87, 10.1016/0012-365X(92)90593-5 Kawarabayashi, 2004, A theorem on paths in locally planar triangulations, European J. Combin., 25, 781, 10.1016/j.ejc.2003.06.004 Lebesgue, 1940, Quelques conséquences simples de la formule d'Euler, J. Math., 9, 27 Lou, 1990, On the 2-extendability of planar graphs, Acta Sci. Natur. Univ. Sunyatseni, 29, 124 Parsons, 1987, Orientably simple graphs, Math. Slovaca, 37, 391 Plummer, 1980, On n-extendable graphs, Discrete Math., 31, 201, 10.1016/0012-365X(80)90037-0 Plummer, 1986, Matching extension in bipartite graphs, 245 Plummer, 1989, A theorem on matchings in the plane, vol. 41, 347 Plummer, 1992, Extending matchings in planar graphs IV, Discrete Math., 109, 207, 10.1016/0012-365X(92)90292-N Sanders, 1997, On paths in planar graphs, J. Graph Theory, 24, 341, 10.1002/(SICI)1097-0118(199704)24:4<341::AID-JGT6>3.0.CO;2-O Thomassen, 1993, Five-coloring maps on surfaces, J. Combin. Theory Ser. B, 59, 89, 10.1006/jctb.1993.1057 White, 1984, Graphs, Groups and Surfaces, vol. 8 Youngs, 1963, Minimal imbeddings and the genus of a graph, J. Math. Mech., 12, 303 Yu, 1997, Disjoint paths, planarizing cycles, and spanning walks, Trans. Amer. Math. Soc., 349, 1333, 10.1090/S0002-9947-97-01830-8