作　　者： ; ; ; ;

机构地区： 广西科学院

出　　处： 《广西科学》 2006年第4期249-252,共4页

摘　　要： 对于无向简单图G及正整数a1,…,ak,记G→(a1,…,ak)v当且仅当对于图G的任意一种顶点k染色,一定对某个i∈{1,…,k}存在顶点全染着颜色i的完全子图Kai.对于p>m ax{a1,…,ak},定义Fv(a1,…,ak;p)=m in{V(G):G→(a1,…,ak)v,Kp G}为顶点Folkm an数.证明关于顶点Folkm an数Fv(k,k;k+1)的新的迭代不等式,并推广K olev和N enov的一个关于多色顶点Folkm an数的不等式. For an undirected, simple graph G, and positive integers α1,…,αk we write G→（α1,…,αk）^vif and only if for every vertex k-coloring of G,there exists a monochromatic Kaj, for some color i∈ {1 ,… ,k}. The vertex Folkman number is defined as Fv（α1,…,αk;p） =min { [V（G）[：G→（α1, …, αk）^v, Kp C G ） for p〉 max { α1…αk, … ak }. In this paper, new recurrent inequalities on vertex Folkman numbers Fv（k,k;k ＋ 1） are proved. We also generalize an inequality of Kolev and Nenov on multicolor Folkman numbers.

关 键 词： 顶点 数 上界 染色

领　　域： [理学] [理学]