| Abstrakt: | Graph $G$ is said to be equimatchable, if every matching in $G$ extends to (i.e., is a subset of) a maximum matching. In the paper
[K. Kawarabayashi and M. D. Plummer. Bounding the size of
equimatchable graphs of fixed genus. Graphs and Combinatorics, 25(1):91--99, 2009.] it is showed that for any fixed $g$, there are only finitely many $3$-connected equimatchable graphs $G$ embeddable in the surface of genus $g$ with the property that either $G$ is non-bipartite or the embedding has representativity at least three. The proof is based on a result that the maximum size of such a graph is at most $c\cdot g^{3/2}$, where $c$ is a constant. In this thesis we show that the upper bound on the number of vertices of a $2$-connected, non-bipartite, equimatchable graph embeddable in the surface of genus $g$ is between $5\sqrt{g} + 6$ and $4\sqrt{g} + 17$ for any $g \leq 2$, between $5\sqrt{g} + 6$ and $12\sqrt{g} + 5$ for any $g\geq 3$, and between $5\sqrt{g}+6$ and $8\sqrt{g} + 5$ for $g\geq 63$. Our methods are based on and refine the concept of isolating matchings used in the aforementioned paper.
Moreover, we provide additional results concerning the structure of factor-critical equimatchable graphs and graphs embeddable in a fixed surface.
|
|---|