轮和扇三类联图的邻点被扩展和可区别全染色

轮和扇三类联图的邻点被扩展和可区别全染色*

张辉1，陈祥恩1，王治文2

【摘 要】探讨了轮与轮的联图的邻点被扩展和可区别全染色，并得到了它的邻点被扩展和可区别全色数，然后通过删边的方法分别得到了扇与轮的联图，扇与扇的联图的邻点被扩展和可区别全染色及它们的邻点被扩展和可区别全色数。 【期刊名称】中山大学学报（自然科学版） 【年(卷),期】2019(058)003 【总页数】8

【关键词】联图；邻点被扩展和可区别全染色；邻点被扩展和可区别全色数 基金项目：国家自然科学基金(11761064, 61163037, 11261046)；宁夏自然科学基金(2018AAC03055)；宁夏回族自治区百人计划

Karoski等首先在文[1]中介绍和研究了图的邻和可区别一般边染色，其后，Przybylo等在文[2]中进一步提出邻和可区别一般全染色，且在文[3-6]中得出相关结论与猜想。最后，Evely-ne Flandrin等在此基础上提出邻点被扩展和可区别全染色，且得出相关结论与猜想。在下文中我们对两轮之联,扇与轮的联及两扇之联的邻点被扩展和可区别全染色进行研究与讨论。

图G的一个全k-染色是指k种颜色对图G的全体顶点及边的一个分配。 设

c

是图

G

的一个全

k-染色，任意的

x∈V(G)，称

w(x)=∑exc(e)+∑y∈N(x)c(y)为点x的扩展和，其中N(x)={y∈V(G)|xy∈E(G)}。称图G的全k-染色c为邻点被扩展和可区别(简记为NESD)，如果w(x)≠w(y)，其中xy∈E(G)。

使得图G存在NESD全k-染色中k的最小值被称为图G的邻点被扩展和可区