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

Datum objave: 30. 6. 2020
Seminar za diskretno matematiko
Četrtek, 2. 7. 2020, ob 10:00, na daljavo

Povezava do seminarja (Zoom):

Time:10:00 (Ljubljana), Thursday, Jul 2nd
ID:920 274 52557

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