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 Ks, 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) = maxG(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