Random Structures and Algorithms · 2004 · 53 citations · 7 references
Natural SciencesMathematicsCombinatoricsGraph AlgorithmsGraph TheoryClique AlgorithmsClique StructureRandom Graph ModelsRandom Graph TheoryRandom GraphsSparse Random Graphs
Abstract This paper investigates the addition of random edges to arbitrary dense graphs; in particular, we determine the number of random edges required to ensure various monotone properties including the appearance of a fixed size clique, small diameter and k ‐connectivity. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2004
7
Endre Szemerédi · Defense Technical Information Center (DTIC) · 1975 · 806 citations
The chromatic number of random graphs
B Bollobás · COMBINATORICA · 1988 · 371 citations
The chromatic number of random graphs
Tomasz Łuczak · COMBINATORICA · 1991 · 195 citations · Full text
On the independence number of random graphs
Alan Frieze · Discrete Mathematics · 1990 · 192 citations