Bojan Mohar: Can the genus of a graph be approximated?
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 https://scmscomb.github.io/