SEMINAR: Groups and Combinatorics Seminar: Generalized Thrackle and Graph Surface Embeddings

Time and place: 15:00 Friday 6 November in MLR1.

Speaker: Yian Xu (University of Western Australia)

Title: Generalized Thrackle and Graph Surface Embeddings

Abstract: A thrackle on a surface X is a graph of size e and order n drawn on X such that every two distinct edges of G meet exactly once either at their common endpoint, or at a proper crossing. An unsolved conjecture of Conway (1969) asserts that e is at most n for every thrackle on a sphere. Until now, the best known bound is that e is at most 1.428n. By using discharging rules we show that e is at most 1.4n. Furthermore we show that the following are equivalent: G has a drawing on X where every two edges meet an odd number of times (a generalized thrackle); G has a drawing on X where every two edges meet exactly once (a one-thrackle); G has a special embedding on a surface whose genus differs from the genus of X by at most one.