zbMATH — the first resource for mathematics

The chromatic number of random graphs. (English) Zbl 0666.05033
Let \(G_ p\) denote a random graph with vertex set \(\{\) 1,2,...,n\(\}\), in which the edges are chosen independently and with probability \(p=p(n)\), \(0<p<1\). The main aim of the paper is the study of the clique number \(cl(G_ p)\) and chromatic number \(\chi (G_ p)\) of \(G_ p\) for p constant. The notation and terminology used are standard. It is proved that for a fixed probability p, \(0<p<1\), almost every random graph \(G_{n,p}\) has chromatic number \[ (+o(1))\log (1/(1-p))\frac{n}{\log n}. \] This result improves the estimation of \(\chi (G_ p)\) presented in D. W. Matula [ibid. 7, 275-284 (1987; Zbl 0648.05049)] and is best possible. Further, some results concerning independent sets and the chromatic number of graphs \(G_ p\) for varying probabilities are sketched.
Reviewer: U.Baumann

05C15 Coloring of graphs and hypergraphs
05C80 Random graphs (graph-theoretic aspects)
Full Text: DOI
[1] K. Azuma, Weighted sums of certain dependent random variables,Tôhoku Math. J.,3 (1967), 357–367. · Zbl 0178.21103 · doi:10.2748/tmj/1178243286
[2] B. Bollobás, The evolution of sparse graphs,in Graph Theory and Combinatorics, Proc. Cambridge Combinatorial Conf. in honour of Paul Erdos (B. Bollobás, ed.), Academic Press, London, 1984, 35–37. · Zbl 0552.05047
[3] B. Bollobás,Random Graphs, Academic Press, London, 1985, xvi+447 pp.
[4] B. Bollobás andP. Erdos, Cliques in random graphs,Math. Proc. Cambridge Phil. Soc.,80 (1976), 419–427. · Zbl 0344.05155 · doi:10.1017/S0305004100053056
[5] B.Bollobás and A. G.Thomason, Random graphs of small order,in Random Graphs, Annals of Discr. Math., 1985, 47–97. · Zbl 0588.05040
[6] P. Erdos andJ. Spencer,Probabilistic Methods in Combinatorics, Academic Press, New York and London, 1974. · Zbl 0308.05001
[7] D. Freedman, On tail probabilities for martingales,Ann. Probab.,3 (1975), 100–118. · Zbl 0313.60037 · doi:10.1214/aop/1176996452
[8] G. R. Grimmett andC. J. H. McDiarmid, On colouring random graphs,Math. Proc. Cambridge Phil. Soc.,77 (1975), 313–324. · Zbl 0297.05112 · doi:10.1017/S0305004100051124
[9] W. B. Johnson andG. Schechtman, Embeddingl p m intol 1 n ,Acta Math.,150 (1983), 71–85.
[10] C. J. H.McDiarmid, Colouring random graphs badly,in Graph Theory and Combinatorics (R. J. Wilson, ed.), Pitman Research Notes in Mathematics,34 (1979), 76–86. · Zbl 0442.05024
[11] C. J. H. McDiarmid, On the chromatic forcing number of a random graph,Discrete Appl. Math.,5 (1983), 123–132. · Zbl 0508.05055 · doi:10.1016/0166-218X(83)90022-7
[12] D. W. Matula, Expose-and-merge exploration and the chromatic number of a random graph,Combinatorica,7 (1987), 275–284. · Zbl 0648.05049 · doi:10.1007/BF02579304
[13] B. Maurey, Construction de suites symétriques,Compt. Rend. Acad. Sci. Paris 288 (1979), 679–681. · Zbl 0398.46019
[14] V. D.Milman and G.Schechtman,Asymptotic Theory of Finite Dimensional Normed Spaces, Lecture Notes in Mathematics, vol. 1200, Springer-Verlag, 1986, viii+156 pp. · Zbl 0606.46013
[15] G. Pisier, On the dimension ofl p n -subspaces of Banach spaces, for 1<p<2,Trans. Amer. Math. Soc.,276 (1983), 201–211. · Zbl 0509.46016
[16] E. Shamir andJ. Spencer, Sharp concentration of the chromatic number of random graphsG n,p,Combinatorica,7 (1987), 121–129. · Zbl 0632.05024 · doi:10.1007/BF02579208
[17] G. Schechtman, Random embeddings of euclidean spaces in sequence spaces,Israel J. Math.,40 (1981), 187–192. · Zbl 0474.46004 · doi:10.1007/BF02761909
[18] E. Shamir andR. Upfal, Sequential and distributed graph colouring algorithms with performance analysis in random graph spaces,J. of Algorithms 5 (1984), 488–501. · Zbl 0564.05030 · doi:10.1016/0196-6774(84)90003-8
[19] W. F. De La Vega, On the chromatic number of sparse random graphs,in Graph Theory and Combinatorics, Proc. Cambridge Combinatorial Conf. in honour of Paul Erdos (B. Bollobás, ed., Academic Press, London, 1984, 321–328.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.