集染色顶点和集染色边的Folkman数（英文）

On the Set-coloring Vertex and Edge Folkman Numbers

对于给定的简单图G和正整数a1,a2,…,ak,G→(a1,a2,…,ak)vr(G→(a1,a2,…,ak)er)是指,对于V(G)(E(G))的任意k-染色,其中每个顶点(边)被用{1,…,k}的一个r-子集来染色,存在i∈{1,…,k}和一个阶为ai的完全子图,其中每个顶点(边)被一个包含颜色i的r-子集染色.本文在整数t>max{a1,a2,…,ak}的条件下,定义并研究下述集染色顶点(边)Folkman数:F(r)v(a1,a2,…,ak;t)=min{|V(G)|:G→(a1,a2,…,ak)vr且KtG}(类似地,F(r)e(a1,a2,…,ak;t)=min{|V(G)|:G→(a1,a2,…,ak)er且KtG}).

Given a simple graph Gand positive integers a1,a2,…,ak,we write G →(a1,a2,…,ak)vr(resp.G →(a1,a2,…,ak)er)if for any k-coloring of V(G)(resp.E(G))in which each vertex(edge)is colored with an r-subset of{1,…,k}.There exists a complete subgraph of order aiin which every vertex(resp.edge)is colored with an r-subset containing color i for some i∈ {1,…,k}.In this paper,for integer t> max{a1,a2,…,ak},the set-coloring vertex(resp.edge)Folkman number is defined and studied,F(r)v(a1,a2,…,ak;t)= min{|V(G)|:G→(a1,a2,…,ak)vrand KtG}(resp.F(r)e(a1,a2,…,ak;t)= min{|V(G)|:G →(a1,a2,…,ak)erand Kt G}.)