Removal of subgraphs and perfect matchings in graphs on surfaces
Robert E. L. Aldred, Jun Fujisawa · Journal of Graph Theory · 2022
Abstract Let be the Euler characteristic of a surface . We characterize the set of graphs of order at most 6 which satisfies the following: If is a 5‐connected graph embedded in a surface of face‐width at least and is a subgraph of isomorphic to such that has even order, then has a perfect matching. An analogous result on near‐perfect matching is given as well. Moreover, we show the following result. Let be a 5‐connected graph embedded in a surface and let be connected subgraphs of of size at most which lie pairwise sufficiently far apart in the face‐subdivision of . We prove that, if the face‐width of is at least and satisfies for each with , then satisfies as well, where is said to satisfy if has at most components for every . It is also shown that the distance condition can be considerably weakened when triangulates the surface. All of these results generalize previous studies on matching extension in graphs on surfaces.