若干图的集合点染色

图G的集合点染色是集合X中的非空子集在点集V(G)上的一个分配,满足相邻点的色集合不相同、相邻点上色集合交不为空集,且每个点上的色集合长度不低于该点的度.此时把X中包含颜色的最小数目称为图G的集合点色数.应用构造染色函数法和色集合分配法研究圈、路、轮、扇、星以及路与路的联图,得到确切的集合点色数,进一步推出圈与圈的联图、路与圈的联图的集合点色数.

广义-Mycielski图的集合点色数

图G的集合点染色是集合X中的非空子集在点集V(G)上的一个分配,满足相邻点的色集合不相同、相邻点上色集合交不为空集,且每个点上的色集合长度不低于该点的度,此时把X中包含颜色的最小数目称为图G的集合点色数.文章应用构造染色函数法给出了两类广义-Mycielski图的集合点染色及其色数.

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

图G的一个集合边染色是边集E(G)到集合X中的非空子集的一个映射f,并且满足对图G中任意两条相邻的边e 1,e 2,有f(e 1)≠f(e 2)且f(e 1)∩f(e 2)≠,将集合X中的最小长度称为图G的集合边色数.通过引进集合矩阵,并利用构造染色矩阵的方法,得到了圈与路、路与路、圈与圈的笛卡尔积图的集合边色数.

图的2-强点可区别全色数的上界

图的2-强点可区别全染色是满足2-距离以内的点可区别的正常全染色,其中色集合为点及其关联元素所染颜色构成的集合.图的2-强点可区别全色数是满足2-强点可区别全染色所用的最小颜色数.应用Lovász局部引理得到了图G的2-强点可区别全色数的上界.确切地,对不含孤立边的简单图G都有χ2-svdt(G)≤35d^2,其中d为G的最大度.