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

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/