A Folkman Linear Family

الأصل · EN

For graphs F and G, let F→ (G,G) signify that any red/blue edge coloring of F contains a monochromatic G. Define Folkman number f(G;p) to be the smallest order of a graph F such that F→ (G,G) and ω(F) ≤ p. It is shown that f(G;p)≤ cn for graphs G of order n with Δ(G)≤ Δ, where Δ≥ 3, c=c(Δ) and p=p(Δ) are positive constants.