几类平面图的集合色数

The Set Chromatic Number of Some Planar Graphs

设G是非平凡连通图,记c:V(G)→N是G的一个顶点染色,这里相邻的两个顶点可以着相同的颜色。对于图G的任一顶点ν,与ν相邻的顶点所着颜色的集称为邻色集,记NC(ν)。如果G中任意相邻的两个顶点ν,u满足NC(u)≠NC(ν),则称c是G的一个集合染色。集合染色所需的最少的颜色数称为G的集合色数,记χs(G)。本文给出了团数是3的平面图,没有4圈的平面图及烟花图和风车图的集合色数。

For a nontrivial connected graph G,let c：V（G）→N be a vertex coloring of G where adjacent vertexes may be colored the same.For a vertex ν of G,the neighborhood color set NC（ν） is the set of colors of the neighbors of ν.The coloring c is called a set coloring if NC（ν）≠NC（u） for every pair u,ν of adjacent vertexes of G.The minimum number of colors required of such a coloring is called the set chromatic number χs（G） of G.This paper gives the set chromatic numbers of some planar graphs,which contain the planar graphs of its clique number is 3,the planar graphs without 4-cycles,fireworks graphs and windmill graphs.