最大度为3或4的图的邻和可区别全染色
Neighbor sum distinguishing total coloring of graphs with maximum degree 3 or 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).
Abstract: 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. Pil?niak and Wo?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