两个多色顶点Folkman数的界

作者：邵泽辉; 许晓东; 罗海鹏

来源：计算机应用研究, 2009, 26(03): 834-835.

DOI：10.3969/j.issn.1001-3695.2009.03.009

• 顶点Folkman数
• 顶点着色
• 上界
• 下界

对于正整数a1,a2,…,ar以及无向简单图G,当且仅当对G的任意一种顶点r着色,都对某个i∈{1,2,…,r}存在顶点都着有颜色i的ai阶的完全子图,则记G→(a1,a2,…,ar)v。对于k>max{a1,a2,…,ar},顶点Folkman数定义为Fv(a1,a2,…,ar;k)=min{|V(G)|:G→(a1,a2,…,ar)v,Kk G}。借助于计算机得到了18≤Fv(2,2,2,3;4)≤Fv(2,3,3;4)≤30。

• 单位
  华中科技大学; 广西科学院