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

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