Neighbor sum distinguishing total coloring of planar graphs without 4-cycles

作者：Song, Hongjie; Xu, Changqing^*

来源：Journal of Combinatorial Optimization, 2017, 34(4): 1147-1158.

DOI：10.1007/s10878-017-0137-x

• Neighbor sum distinguishing total coloring
• Combinatorial Nullstellensatz
• Planar graph

Let G = (V, E) be a graph and phi : V boolean OR E -> {1, 2,..., kappa} be a proper total coloring ofG. Let f (v) denote the sum of the color on a vertex v and the colors on all the edges incident with v. The coloring phi is neighbor sum distinguishing if f (u) not equal f (v) for each edge uv is an element of E(G). The smallest integer kappa in such a coloring of G is the neighbor sum distinguishing total chromatic number of G, denoted by chi ''(Sigma) (G). Pil ' sniak and Wo ' zniak conjectured that chi ''(Sigma) (G) = <= (G) + 3 for any simple graph. By using the famous Combinatorial Nullstellensatz, we prove that chi ''(Sigma) (G) <= max{Delta (G) + 2, 10} for planar graph G without 4-cycles. The bound Delta (G) + 2 is sharp if Delta (G) >= 8.

• 出版日期2017-11
• 单位河北工业大学