##
**Zentralblatt MATH**

**Publications of (and about) Paul Erdös**

**Zbl.No: ** 504.05052

**Autor: ** Erdös, Paul; Fajtlowicz, Siemion

**Title: ** On the conjecture of Hajos. (In English)

**Source: ** Combinatorica 1, 141-143 (1981).

**Review: ** *G.Hajós* [Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg, Math.-Naturw. Reihe 10, 113-117 (1961; Zbl 094.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 *P.A.Catlin* [J. Comb. Theory, Ser. B 26, 268-274 (1979; Zbl 385.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.

**Reviewer: ** K.Schürger

**Classif.: ** * 05C80 Random graphs

05C15 Chromatic theory of graphs and maps

60C05 Combinatorial probability

**Keywords: ** s-chromatic graph; chromatic number; subdivision; labelled graphs

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag