Michal Kotrbčík: Maximum genus - old problem and new results.

Povzetek

In this talk we discuss the problem of determining the maximum integer k such that a given graph has an embedding into the orientable surface of genus k. This integer is known as the  maximum genus of a graph and can be characterised combinatorially, without referring to surfaces.

Using such characterisations, we derive four types of results. First, we present a new simple 2-approximation algorithm for the maximum genus.

Second, we investigate the matching number of the intersection graph of fundamental cycles with respect to different spanning trees of a graph.

Third, we show that the maximum genus can provide both lower and upper linear bound on the maximum number of pairwise vertex-disjoint cycles of a graph.

Finally, we show how one can easily obtain lower and upper bounds on the maximum genus of graphs from particular classes, for example, graphs with fixed girth and minimum degree.