最大度为3或4的图的邻和可区别全染色

• 作者: 姚京京 徐常青
• 来源期刊: 山东大学学报（理学版）
• 学科: 数学
• 关键词: 邻和可区别全染色 最大平均度 组合零点定理
• 年，卷（期）: 2015,（2）
• 页码范围: 9-13
• 页数: 5页
• 分类号: O157
• 字数: 4306字
• 语种: 中文
• DOI: 10.6040/j.issn.1671-9352.0.2014.362

摘要

图 G 的一个正常[k]-全染色是一个映射：V∪E→｛1，2，…，k｝，使得 V∪E 中任意一对相邻或者相关联元素染不同颜色。用 f（v）表示点 v 及所有与其关联的边的颜色的加和，若对任意 uv∈E（G），有 f（u）≠f（v），则称该染色为图 G 的[k]-邻和可区别全染色。k 的最小值称作图 G 的邻和可区别全色数，记为 tndiΣ（G）。Pils＇niak 和Woz＇niak 提出猜想：对任意简单图 G，有 tndiΣ（G）≤Δ（G）＋3，其中Δ（G）为图 G 的最大度。图 G 的最大平均度，记为 mad（G），是 G 的所有非空子图的平均度的最大值。运用组合零点定理和权转移方法，证明了若Δ（G）＝3且mad（G）＜125，或Δ（G）＝4且 mad（G）＜52，则 tndiΣ（G）≤Δ（G）＋2。

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	徐常青	河北工业大学理学院	16	19	2.0	3.0
2	姚京京	河北工业大学理学院	3	9	2.0	3.0