# Bojan Mohar: Can the genus of a graph be approximated?

Source: Discrete mathematics seminar

**Povezava do seminarja (Zoom):
**

https://zoom.com.cn/j/92027452557

Time:10:00 (Ljubljana), Thursday, Jul 2nd

ID：920 274 52557

Password:121323

**Povzetek. **The genus g(G) of a graph G is defined as the minimum genus of a surface
in which G can be embedded (drawn without crossings). Thomassen proved
that it is NP-hard to determine whether g(G) < k, when the graph G and
an integer k are given to us as the input. Robertson and Seymour (and
the speaker) proved that this problem is FPT (fixed-parameter
tractable). However, it is wide open whether the value of g(G) can be
approximated.

The speaker will give an overview of this problem, describe underlying conjectures, and present a complete solution for the case when the graph is dense. The solution uses Szemeredi Regularity Lemma and a result on the genus of quasi-random graphs.

This is joint work with Yifan Jing.

Predavanje je v okviru SCMS Combinatorics Seminar (Shanghai Center for Mathematical Sciences). Več informacij na https://scmscomb.github.io/