Chromatic number, clique subdivisions, and the conjectures of Hajós and Erdős-Fajtlowicz (Q2448966)

For a graph \(G\), let \(\chi(G)\) denote its chromatic number, \(\sigma (G)\) denote the largest integer \( p\) such that \(G\) contains a subdivision of a complete graph of order \( p\) and \(H(n)\) be the maximum of \(\chi (G)/\sigma (G)\) over all \(n\)-vertex graphs \(G\). A famous conjecture of Hajós states that \( H(n)\leq 1\) for all positive integers \(n\). This conjecture was disproved by \textit{P. A. Catlin} [J. Comb. Theory, Ser. B 26, 268--274 (1979; Zbl 0385.05033)]. \textit{P. Erdős} and \textit{S. Fajtlowicz} [Combinatorica 1, 141--143 (1981; Zbl 0504.05052)] further showed by considering a random graph that \(H(n)\geq cn^{1/2}/\log n\) for some absolute constant \(c>0\) and they conjectured that this bound is tight up to a constant factor in that there is some absolute constant \(C\) such that \(\chi (G)/\sigma (G) \leq Cn^{1/2}/\log n\) for all \(n\)-vertex graphs \(G\). In this paper the authors prove the Erdős-Fajtlowicz conjecture, deducing an estimate on the order of the largest clique subdivision which can be found in every graph on \(n\) vertices with independence number \(\alpha \).