仙人掌图的邻点被扩展和可区别全染色
设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