几种笛卡尔积图的集合边染色

张 明，贾泽乐，李沐春

(1. 兰州交通大学 电子与信息工程学院，兰州 730070；2. 兰州交通大学 应用数学研究所，兰州 730070)

1 引言

图染色是图论中的一个重要分支,在电路设计、交通运输和网络分析等方面都有着非常广泛的应用.图的染色理论有很多分支，其中包括点染色、边染色、全染色以及在此基础上添加其他约束条件所产生的一些特殊染色等.近年来,集合染色已经成为学者们关注的焦点.2009年,Hegde[1]提出了集合染色的概念,即给定图G的一个从点集V(G)到集合X中一个非空子集的映射f,其中X={1,2,…,k},k为正整数,如果满足对图G中任意的两个相邻的点u,v，有f(u)≠f(v)，则称f是图G的一个集合点染色，并将集合X中包含颜色的最小数目k称为集合点色数，记为χS(G).2010年,Boutin等[2]定义了强集合染色的概念,即在满足集合染色的前提下，边的颜色是通过与其关联的两个顶点做对称差，同时集合X中的非空子集分别只在顶点和边上表现一次,同时他们对路和完全二叉树进行了研究，并得到了这两类图的强集合色数均不超过4.2011年，Balister等[3]通过对图进行点边划分,从而找到了几类满足集合染色的特殊图.王艳丽[4]研究了向日葵图和风车图的集合色数并给出了团数是3的平面图,没有4圈的平面图及烟花图的集合色数[5].2012年，王艳丽等[6]运用结构图论的方法，给出了集合边色数的下界以及图与其顶点删除子图、边删除子图的集合边色数的关系.2013年,王艳丽等[7]运用分析的方法证明了路与扇的笛卡尔积图的集合边……