山东大学学报（理学版）
山東大學學報（理學版）
산동대학학보（이학판）
JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE)
2015年
2期
9-13
,共5页
邻和可区别全染色%最大平均度%组合零点定理
鄰和可區彆全染色%最大平均度%組閤零點定理
린화가구별전염색%최대평균도%조합영점정리
neighbor sum distinguishing total coloring%maximum average degree%Combinatorial Nullstellensatz
图 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。
圖 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。
도 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。
A proper [k]-total coloring of a graph G is a map :V∪E→{1,2,…,k}such that (x)≠(y)for each pair of adjacent or incident elements x,y∈V∪E.Let f(v)denote the sum of the color of vertex v and the colors of the edges incident with v.A [k]-neighbor sum distinguishing total coloring of G is a [k]-total coloring of G such that for each edge uv∈E(G),f(u)≠f(v).Let tndiΣ(G)denote the smallest value k in such a coloring of G.Pils'niak and Woz'niak first introduced this coloring and conjectured that tndiΣ(G)≤Δ(G)+3 for any simple graph with maximum degree Δ(G).The maximum average degree of G is the maximum of the average degree of its non-empty subgraphs, which is denoted by mad(G).By using the Combinatorial Nullstellensatz and the discharging method,it is proved that if G is a graph with Δ(G)=3 and mad(G)<125 ,or Δ(G)=4 and mad(G)<52 ,then tndiΣ(G)≤Δ(G)+2.
