关键词: 邻和可区别全染色, 最大平均度, 组合零点定理

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.

Key words: neighbor sum distinguishing total coloring, maximum average degree, Combinatorial Nullstellensatz