Chromatic thresholds in sparse random graphs

Authors:

Abstract: The chromatic threshold

d e l t a_{c} h i (H, p)

of a graph

H

with respect to the random graph

G (n, p)

is the infimum over

d > 0

such that the following holds with high probability: the family of

H

-free graphs

G s u b s e t G (n, p)

with minimum degree

d e l t a (G) g e d p n

has bounded chromatic number. The study of

d e l t a_{c} h i (H) := d e l t a_{c} h i (H, 1)

was initiated in 1973 by ErdH{o}s and Simonovits. Recently

d e l t a_{c} h i (H)

was determined for all graphs

H

. It is known that

d e l t a_{c} h i (H, p) = d e l t a_{c} h i (H)

for all fixed

p i n (0, 1)

, but that typically

d e l t a_{c} h i (H, p) e d e l t a_{c} h i (H)

if

p = o (1)

. Here we study the problem for sparse random graphs. We determine

d e l t a_{c} h i (H, p)

for most functions

p = p (n)

when

H i n K_{3}, C_{5}

, and also for all graphs

H

with

c h i (H) o t i n 3, 4

.

Recommendations

Cited In (6)

This page was built for publication: Chromatic thresholds in sparse random graphs