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

Books Problems Set Theory Combinatorics Extremal Probl/Ramsey Th.
Graph Theory Add.Number Theory Mult.Number Theory Analysis Geometry
Probabability Personalia About Paul Erdös Publication Year Home Page