
doi: 10.1007/bf02579269
\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.
labelled graphs, Coloring of graphs and hypergraphs, Combinatorial probability, chromatic number, subdivision, Random graphs (graph-theoretic aspects), s-chromatic graph
labelled graphs, Coloring of graphs and hypergraphs, Combinatorial probability, chromatic number, subdivision, Random graphs (graph-theoretic aspects), s-chromatic graph
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 35 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 1% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
