On the growth rate of chromatic numbers of finite subgraphs

Abstract

We prove that, for every function $f:\mathbb{N}\to \mathbb{N}$, there is a graph $G$ with uncountable chromatic number such that, for every $k\in \mathbb{N}$ with $k\ge 3$, every subgraph of $G$ with fewer than $f(k)$ vertices has chromatic number less than $k$. This answers a question of Erdős, Hajnal, and Szemeredi.

arXiv comment10 pages