杨随义,杨晓亚,唐保祥,何万生
(天水师范学院 数学与统计学院,甘肃 天水 741001)
*两类3-正则图的邻点可区别I-全染色
杨随义,杨晓亚,唐保祥,何万生
(天水师范学院 数学与统计学院,甘肃 天水 741001)
图G的I-全染色是指若干种颜色对图G的顶点和边的一个分配,使得任意两个相邻的点的颜色不同,任意两条相邻的边的颜色不同.在图G的一个I-全染色下,G的任意一个点的色集合是指该点的颜色以及与该点相关联的全体边的颜色构成的集合.图G的一个I-全染色称为是邻点可区别的,如果任意两个相邻点的色集合不相等.对一个图G进行邻点可区别I-全染色所用的最少颜色的数目称为图G的邻点可区别I-全色数.本文给出了两类3-正则图的邻点可区别I-全色数.
I-全染色;邻点可区别I-全染色;邻点可区别I-全色数
图的染色是图论的重要研究内容之一,由计算机科学和信息科学等所产生的点可区别边染色[1],邻点可区别边染色(或邻强边染色)[2],及邻点可区别全染色[3-6]等都是十分困难的问题,至今文献甚少.在此基础上,进一步提出了图的新染色概念.图的邻点可区别I-全染色是其中之一[7],本文给出了两类3-正则图的邻点可区别I-全色数.
定义1.1[6]设G是阶至少为2的连通图,k为正整数,f是图G的使用颜色为1,2,…,k的正常全染色.对∀x∈V(G),令C(x)表示在f下点x的颜色及与x关联的全体边的颜色构成的集合,称之为在全染色f下点x的色集合,令¯C(x)={1,2,…,k}\C(x).如果∀uv∈E(G),有C(u)≠C(v),则f称为G的k-邻点可区别全染色.称

为G的邻点可区别全……