Upper bounds for the vertex Folkman number F-v(3,3,3;4) and F-v(3,3,3;5)

作者：Deng, Fei^*; Liang, Meilian; Shao, Zehui; Xu, Xiaodong

来源：Ars Combinatoria, 2013, 112: 249-256.

For positive integers t and k, the vertex(resp. edge) Folkman number F-v(t, t, t; k) (resp. F-e(t, t, t; k)) is the smallest integer n such that there is a K-k-free graph of order n for which any three coloring of its vertices(resp. edges) yields a monochromatic copy of K-t. In this note, an algorithm for testing (t, t, ..., t)(v) in cyclic graphs is presented and it is applied to find new upper bounds for some vertex or edge Folkman numbers. By using this method, we obtain F-v(3, 3, 3; 4) <= 66 and F-v(3, 3,3; 5) <= 24, which leads to F-v(6, 6,6; 7) <= 726 and F-e(3, 3, 3; 8) <= 727.

• 出版日期2013-10
• 单位广西科学院; 成都理工大学; 广西大学; 成都大学