Tung H Nguyen, Princeton University

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.

See: https://sites.google.com/view/rutgersdmseminar