A Folkman Linear Family
A Folkman Linear Family
复制标题
DOI：
10.1137/130947647
复制
发表时间：
2014-09
期刊：
影响因子：
--
通讯作者：
Qizhong Lin;Yusheng Li
中科院分区：
文献类型：
--
作者：
Qizhong Lin;Yusheng Li
对于图$F$和$G$，令$F\to（G，G）$表示$F$的任何红/蓝边着色包含单色$G$。定义Folkman数$f（G;p）$为图$F$的最小阶，使得$F\to（G，G）$且$\omega（F）\lep $。证明了$f（G; p）\le cn$，其中$\Delta（G）\le \Delta$，$c=c（\Delta）$，$p=p（\Delta）$是正常数。
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.