Chromatic number and regular subgraphs

Abstract In 1992, Erdős and Hajnal posed the following natural problem: Does there exist, for every , an integer such that every graph with chromatic number at least contains edge‐disjoint cycles on the same vertex set? We solve this problem in a strong form, by showing that there exist ‐vertex graphs with fractional chromatic number that do not even contain a 4‐regular subgraph. This implies that no such number exists for . We show that, assuming a conjecture of Harris, the bound on the fractional chromatic number in our result cannot be improved. (After our paper was written, Harris' conjecture was proved by Martinsson.)