BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Bojan Mohar (Simon Fraser University)
DTSTART:20200702T080000Z
DTEND:20200702T090000Z
DTSTAMP:20260423T035022Z
UID:SCMSComb/5
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/SCMSComb/5/"
 >Can the genus of a graph be approximated?</a>\nby Bojan Mohar (Simon Fras
 er University) as part of SCMS Combinatorics Seminar\n\n\nAbstract\nThe ge
 nus g(G) of a graph G is defined as the minimum genus of a surface in whic
 h 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) pro
 ved that this problem is FPT (fixed-parameter tractable). However\, it is 
 wide open whether the value of g(G) can be approximated.\n\nThe speaker wi
 ll give an overview of this problem\, describe underlying conjectures\, an
 d present a complete solution for the case when the graph is dense. The so
 lution uses Szemeredi Regularity Lemma and a result on the genus of quasi-
 random graphs.\n\nThis is joint work with Yifan Jing.\n\npassword 121323\n
LOCATION:https://researchseminars.org/talk/SCMSComb/5/
END:VEVENT
END:VCALENDAR