×

Colourings of random graphs. (English) Zbl 0693.05030

Graph colourings, Proc. Conf., Milton Keynes/UK 1988, Pitman Res. Notes Math. Ser. 218, 79-86 (1990).
[For the entire collection see Zbl 0693.05025.]
From the authors Introduction: “Our aim here is to survey the flurry of exciting recent developments on colourings of random graphs, concerning vertex colourings, edge colourings and total colourings. The chapter breaks naturally into three further sections. First we discuss the vertex chromatic number \(\chi (G_{n,p})\), and in particular the beautiful work of Bollobás which pins down the asymptotic behaviour of this quantity. Then follows a short section on edge colourings, in which we consider how rare class 2 graphs are - that is, graphs with \(\chi '>\Delta\). Finally we discuss total colourings, and show that \(\chi ''>\Delta +1\) only rarely for random graphs \(G_{n,p}\).”
Reviewer: I.Tomescu

MSC:

05C15 Coloring of graphs and hypergraphs
05C80 Random graphs (graph-theoretic aspects)
05A30 \(q\)-calculus and related topics

Citations:

Zbl 0693.05025