Coloring the edges of a random graph without a monochromatic giant component.

Spöhel, Reto; Steger, Angelika; Thomas, Henning

Displaying similar documents to “Coloring the edges of a random graph without a monochromatic giant component.”

Almost all graphs with 2. 522 $n$ edges are not 3-colorable.

Achlioptas, Dimitris, Molloy, Michael (1999)

The Electronic Journal of Combinatorics [electronic only]

Similarity:

Ramsey Properties of Random Graphs and Folkman Numbers

Vojtěch Rödl, Andrzej Ruciński, Mathias Schacht (2017)

Discussiones Mathematicae Graph Theory

Similarity:

For two graphs, G and F, and an integer r ≥ 2 we write G → (F)r if every r-coloring of the edges of G results in a monochromatic copy of F. In 1995, the first two authors established a threshold edge probability for the Ramsey property G(n, p) → (F)r, where G(n, p) is a random graph obtained by including each edge of the complete graph on n vertices, independently, with probability p. The original proof was based on the regularity lemma of Szemerédi and this led to tower-type dependencies...