The seminars in Discrete Mathematics are aimed at researchers, employees, and students.
This week's seminar is given by Tung Nguyen, Princeton University, US.
Title: Induced subdivisions and polylogarithmic chromatic number
Abstract: We discuss a proof that for every graph H, every n-vertex graph with no induced subdivision of H and with bounded clique number has chromatic number at most polylog(n). This extends a result of Fox and Pach that similar polylogarithmic bounds hold for all string graphs, and is close to optimal as there are triangle-free n-vertex string graphs with chromatic number at least loglog n. Joint work with Alex Scott and Paul Seymour.
