A Folkman Linear Family

Abstract

For graphs $F$ and $G$, let $F\to (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\to (G,G)$ and $\omega (F)\le p$. It is shown that $f(G;p)\le cn$ for graphs $G$ of order $n$ with $\Delta (G)\le \Delta$, where $\Delta \ge 3$, $c=c(\Delta )$ and $p=p(\Delta )$ are positive constants.

11 pages