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

• 作者: 张辉 李泽鹏 陈祥恩
• 来源期刊: 高校应用数学学报
• 学科: 数学
• 关键词: 全k-染色 仙人掌图 邻点被扩展和可区别全染色 邻点被扩展和可区别全色数
• 年，卷（期）: 2019,（3）
• 页码范围: 373-378
• 页数: 6页
• 分类号: O157.5
• 字数: 4173字
• 语种: 中文

摘要

设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猜想对于仙人掌图是成立的.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	陈祥恩	西北师范大学数学与统计学院	155	1069	14.0	28.0
2	张辉	西北师范大学数学与统计学院	41	330	11.0	17.0
3	李泽鹏	兰州大学信息科学与工程学院	4	1	1.0	1.0