DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

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


Authors:

A.J. Dong and T. Li

Title:

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

Source:

Discussiones Mathematicae Graph Theory

Received: 2018-10-11, Revised: 2019-03-27, Accepted: 2019-03-27, https://doi.org/10.7151/dmgt.2221

Abstract:

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.

Keywords:

total coloring, neighbor product distinguishing coloring, planar graph

PDF
Close