# Equimatchable Graphs on Surfaces # Varování

Publikace nespadá pod Lékařskou fakultu, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.
Autoři EIBEN Eduard KOTRBČÍK Michal 2016 Článek v odborném periodiku Journal of Graph Theory http://dx.doi.org/10.1002/jgt.21859 http://dx.doi.org/10.1002/jgt.21859 Informatika graph; matching; equimatchable; factor-critical; embedding; genus; bipartite; degeneracy A graph G is equimatchable if each matching in G is a subset of a maximum-size matching and it is factor critical if G - v has a perfect matching for each vertex v of G. It is known that any 2-connected equimatchable graph is either bipartite or factor critical. We prove that for 2-connected factor-critical equimatchable graph G the graph G\(V(M) U {v}) is either K_{2n} or K_{n,n} for some n for any vertex v of G and any minimal matching M such that {v} is a component of G\V(M). We use this result to improve the upper bounds on the maximum number of vertices of 2-connected equimatchable factor-critical graphs embeddable in the orientable surface of genus g to 4\sqrt{g} + 17 if g <= 2 and to 12\sqrt{g} + 5 if g >= 3. Moreover, for any nonnegative integer g we construct a 2-connected equimatchable factor-critical graph with genus g and more than 4\sqrt{2g} vertices, which establishes that the maximum size of such graphs is \Theta(\sqrt{g}). Similar bounds are obtained also for nonorientable surfaces. In the bipartite case for any nonnegative integers g, h, and k we provide a construction of arbitrarily large 2-connected equimatchable bipartite graphs with orientable genus g, respectively nonorientable genus h, and a genus embedding with face-width k. Finally, we prove that any d-degenerate 2-connected equimatchable factor-critical graph has at most 4d + 1 vertices, where a graph is d-degenerate if every its induced subgraph contains a vertex of degree at most d.

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.