仙人掌图的邻点被扩展和可区别全染色

摘要：

设G为简单图.G的全k-染色是指k种颜色1,2,···,k对图G的全体顶点及边的一个分配.设c是图G的一个全k-染色,任意的x∈V(G),称w(x)=∑e?x c(e)+∑y∈N(x)c(y)为点x的扩展和,其中N(x)={y∈V(G)|xy∈E(G)}.称图G的全k-染色c为邻点被扩展和可区别(简记为N ESD),如果w(x)6=w(y),其中xy∈E(G).使得图G存在NESD全k-染色的最小值k被称为图G的邻点被扩展和可区别全色数,简记为egndi∑(G).本文利用数学归纳法探讨了仙人掌图的邻点被扩展和可区别全染色,并证明了这类图的邻点被扩展和可区别全色数不超过2.该结论说明Flandrin等人提出的NESDTC猜想对于仙人掌图是成立的.

关键词：全k-染色、仙人掌图、邻点被扩展和可区别全染色、邻点被扩展和可区别全色数

所属期刊栏目：34

分类号：O157.5(代数、数论、组合理论)

资助基金：国家自然科学基金11761064, 61163037, 11261046;兰州大学中央高校基本科研业务费专项资金lzujbky-2018-37

在线出版日期：2019-09-23（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：373-378