solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看128次
On the Nonexistence of Some Generalized Folkman Numbers. (arXiv:1705.06268v1 [math.CO])
来源于:arXiv
For an undirected simple graph $G$, we write $G \rightarrow (H_1, H_2)^v$ if
and only if for every red-blue coloring of its vertices there exists a red
$H_1$ or a blue $H_2$. The generalized vertex Folkman number $F_v(H_1, H_2; H)$
is defined as the smallest integer $n$ for which there exists an $H$-free graph
$G$ of order $n$ such that $G \rightarrow (H_1, H_2)^v$. The generalized edge
Folkman numbers $F_e(H_1, H_2; H)$ are defined similarly, when colorings of the
edges are considered.
We show that $F_e(K_{k+1},K_{k+1};K_{k+2}-e)$ and $F_v(K_k,K_k;K_{k+1}-e)$
are well defined for $k \geq 3$. We prove the nonexistence of $F_e(K_3,K_3;H)$
for some $H$, in particular for $H=B_3$, where $B_k$ is the book graph of $k$
triangular pages, and for $H=K_1+P_4$. We pose three problems on generalized
Folkman numbers, including the existence question of edge Folkman numbers
$F_e(K_3, K_3; B_4)$, $F_e(K_3, K_3; K_1+C_4)$ and $F_e(K_3, K_3; \overline{P_2
\cup P_3} )$. Our results lead to some genera 查看全文>>