On Generalized Folkman Numbers
On Generalized Folkman Numbers
复制标题
关于广义福克曼数
DOI：
10.11650/tjm.21.2017.7710
复制
发表时间：
2017-01
影响因子：
0.4
通讯作者：
Lin Qizhong
中科院分区：
文献类型：
--
作者：
Li Yusheng;Lin Qizhong
对于图形$ g $，$ g_1 $和$ g_2 $，让$ g \ to（g_1，g_2）$表示$ g $的任何红色/蓝色边缘色包含红色$ g_1 $或蓝色$ g_2 $ ，让$ f（g_1，g_2）$为最低$ n $，使得有一个图形$ g $ of订单$ n $，with $ \ omega（g）= \ max \ {\ Omega
For graphs $G$, $G_1$ and $G_2$, let $G \to (G_1,G_2)$ signify that any red/blue edge-coloring of $G$ contains a red $G_1$ or a blue $G_2$, and let $f(G_1,G_2)$ be the minimum $N$ such that there is a graph $G$ of order $N$ with $\omega(G) = \max \{\omega(G_1),\omega(G_2)\}$ and $G \to (G_1,G_2)$. It is shown that $c_1(n/\!\log n)^{(m+1)/2} \leq f(K_m,K_{n,n}) \leq c_2 n^{m-1}$, where $c_i = c_i(m) > 0$ are constants. In particular, $cn^2/\log n \leq f(K_3,K_{n,n}) \leq 2n^2+2n-1$. Moreover, $f(K_m,T_n) \leq m^2(n-1)$ for all $n \geq m \geq 2$, where $T_n$ is a tree on $n$ vertices.