On colouring random graphs
- 1 March 1975
- journal article
- research article
- Published by Cambridge University Press (CUP) in Mathematical Proceedings of the Cambridge Philosophical Society
- Vol. 77 (2), 313-324
- https://doi.org/10.1017/s0305004100051124
Abstract
Let ωn denote a random graph with vertex set {1, 2, …, n}, such that each edge is present with a prescribed probability p, independently of the presence or absence of any other edges. We show that the number of vertices in the largest complete subgraph of ωn is, with probability one,Keywords
This publication has 7 references indexed in Scilit:
- On the evolution of random graphsPublished by Walter de Gruyter GmbH ,2011
- Random Graph TheoremsPublished by Springer Nature ,1977
- GRAPH COLORING ALGORITHMS††This research was supported in part by the Advanced Research Projects Agency of the Department of Defense under contract SD-302 and by the National Science Foundation under contract GJ-446.Published by Elsevier ,1972
- GRAPH THEORYPublished by Defense Technical Information Center (DTIC) ,1969
- Majorants of the Chromatic Number of a Random GraphJournal of the Royal Statistical Society Series B: Statistical Methodology, 1969
- An upper bound for the chromatic number of a graph and its application to timetabling problemsThe Computer Journal, 1967
- The Eigenvalues of a Graph and Its Chromatic NumberJournal of the London Mathematical Society, 1967