2019/02/21 by Lambie-Hanson, Chris
#03E05 #05C15 #05C63 #Combinatorics (math.CO) #FOS: Mathematics #Logic (math.LO)
paper · doi:10.48550/arxiv.1902.08177
We prove that, for every function f:ℕ → ℕ, there is a graph G with uncountable chromatic number such that, for every k ∈ ℕ with k ≥ 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.