ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2019: 0.755

SCImago Journal Rank (SJR) 2019: 0.600

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory

Article in press


A.J. Dong and T. Li


Neighbor product distinguishing total colorings of planar graphs with maximum degree at least ten


Discussiones Mathematicae Graph Theory

Received: 2018-10-11, Revised: 2019-03-27, Accepted: 2019-03-27,


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,\dots,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\in E(G)$, if $p(u)\neq 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 $\chi{''}_{\prod}(G)$, we denote the smallest value of $k$ in such a coloring of $G$. It has been conjectured by Li et al. that $\Delta(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 $\Delta(G)\geq10$. Moreover, for planar graph $G$ with $\Delta(G)\geq11$, it is neighbor product distinguishing $(\Delta(G)+2)$-total colorable, and the upper bound $\Delta(G)+2$ is tight.


total coloring, neighbor product distinguishing coloring, planar graph