On the conjecture of Hajos (Q1835686)

\textit{G.Hajós} [Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg, Math.-Naturw. Reihe 10, 113-117 (1961; Zbl 0094.17602), pp. 116-117] conjectured that every \(s\)-chromatic graph contains a subdivision of \(K_s\), the complete graph on \(s\) vertices. This conjecture was disproved ins a paper by \textit{P.A.Catlin} [J. Comb. Theory, Ser. B 26, 268-274 (1979; Zbl 0385.05033)]. In the present paper it is shown by probabilistic methods that the Hajós conjecture fails for almost all graphs. More precisely, let \(G=G(n)\) be a graph of \(n\) vertices. Denote by \(\chi(G)\) the chromatic number of \(G\) and by \(\sigma(G)\) the largest integer \(\ell\) such that \(G\) contains a subdivision of \(K_{\ell}\). Put \(H(G)=\chi(G)/\sigma(G)\) and \(H(n)=\max_{G(n)}H(G(n))\) (hence, the Hajós conjecture says \(H(n)=1\)). In the present paper it is shown that there exists an absolute constant \(c\) such that \(H(n)> C\sqrt n/\log n\) holds for almost all labelled graphs with \(n\) vertices.