Neighbor Product Distinguishing Total Colorings of Planar Graphs with Maximum Degree at least Ten

Discussiones Mathematicae Graph Theory

Dong Aijun¹  Li Tong² 

[1] School of Data and Computer ScienceShandong Women’s University, Jinan, 250300, P.R.China;School of Mathematics, Shandong University, Jinan 250100, P.R.China;

关键词: total coloring;    neighbor product distinguishing coloring;    planar graph;    05c15;   

DOI  :  10.7151/dmgt.2221

来源: DOAJ

【 摘 要 】

A proper [k]-total coloring c of a graph G is a proper total coloring c of G using colors of the set [k] = {1, 2, . . . , k}. Let p(u) denote the product of the color on a vertex u and colors on all the edges incident with u. For each edge uv ∈ E(G), if p(u) ≠ p(v), then we say the coloring c distinguishes adjacent vertices by product and call it a neighbor product distinguishing k-total coloring of G. By X″∏(G), we denote the smallest value of k in such a coloring of G. It has been conjectured by Li et al. that Δ(G) + 3 colors enable the existence of a neighbor product distinguishing total coloring. In this paper, by applying the Combinatorial Nullstellensatz, we obtain that the conjecture holds for planar graph with Δ(G) ≥ 10. Moreover, for planar graph G with Δ(G) ≥ 11, it is neighbor product distinguishing (Δ(G) + 2)-total colorable, and the upper bound Δ(G) + 2 is tight.

【 授权许可】

Unknown