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

作者：姚京京; 徐常青

来源：山东大学学报(理学版), 2015, 50(02): 9-13.

• 邻和可区别全染色
• 最大平均度
• 组合零点定理

图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。

• 单位
  河北工业大学