Induced subgraphs of induced subgraphs of large chromatic number

António Girão, Freddie Illingworth, Emil Powierski, Michael Savery, Alex Scott, Youri Tamitegama, Jane Tan

Published 2022-03-07Version 1

We prove that, for every graph $F$ with at least one edge, there is a constant $c_F$ such that there are graphs of arbitrarily large chromatic number and the same clique number as $F$ in which every $F$-free induced subgraph has chromatic number at most $c_F$. This generalises recent theorems of Bria\'{n}ski, Davies and Walczak, and Carbonero, Hompe, Moore and Spirkl. Moreover, we show an analogous statement where clique number is replaced by odd girth.