A counterexample to a conjecture of Esperet

Benjamin Moore

Charles University

April 7, 2022, 12:20 in S6


Abstract: I'll show that for any integer n, there exists a K_4-free graph G such that G has chromatic number at least n, and every induced subgraph that is triangle free has chromatic number at most 4. Up to changing this 4 to a 3, this is best possible.

Joint work with Alvaro Carbonero, Patrick Hompe, and Sophie Spirkl.