We study the interplay between the maximum genus of a graph and bases of its cycle space via the corresponding intersection graph. Our main results show that the matching number of the intersection graph is independent of the basis precisely when the graph is upper-embeddable, and completely describe the range of matching numbers when the graph is not upper-embeddable. Particular attention is paid to cycle bases consisting of fundamental cycles with respect to a given spanning tree. For $4$-edge-connected graphs, the intersection graph with respect to any spanning tree (and, in fact, with respect to any basis) has either a perfect matching or a matching missing exactly one vertex. We show that if a graph is not $4$-edge-connected, different spanning trees may lead to intersection graphs with different matching numbers. We also show that there exist $2$-edge connected graphs for which the set of values of matching numbers of their intersection graphs contains arbitrarily large gaps.
@article{10_37236_2479,
author = {Michal Kotrb\v{c}{\'\i}k and Martin \v{S}koviera},
title = {Matchings, cycle bases, and the maximum genus of a graph},
journal = {The electronic journal of combinatorics},
year = {2012},
volume = {19},
number = {3},
doi = {10.37236/2479},
zbl = {1252.05179},
url = {http://geodesic.mathdoc.fr/articles/10.37236/2479/}
}
TY - JOUR
AU - Michal Kotrbčík
AU - Martin Škoviera
TI - Matchings, cycle bases, and the maximum genus of a graph
JO - The electronic journal of combinatorics
PY - 2012
VL - 19
IS - 3
UR - http://geodesic.mathdoc.fr/articles/10.37236/2479/
DO - 10.37236/2479
ID - 10_37236_2479
ER -
%0 Journal Article
%A Michal Kotrbčík
%A Martin Škoviera
%T Matchings, cycle bases, and the maximum genus of a graph
%J The electronic journal of combinatorics
%D 2012
%V 19
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/2479/
%R 10.37236/2479
%F 10_37236_2479
Michal Kotrbčík; Martin Škoviera. Matchings, cycle bases, and the maximum genus of a graph. The electronic journal of combinatorics, Tome 19 (2012) no. 3. doi: 10.37236/2479
