Geodesic
Neighbor Product Distinguishing Total Colorings of Planar Graphs with Maximum Degree at least Ten
Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 4, pp. 981-999.

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: total coloring, neighbor product distinguishing coloring, planar graph 
@article{DMGT_2021_41_4_a7,
     author = {Dong, Aijun and Li, Tong},
     title = {Neighbor {Product} {Distinguishing} {Total} {Colorings} of {Planar} {Graphs} with {Maximum} {Degree} at least {Ten}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {981--999},
     publisher = {mathdoc},
     volume = {41},
     number = {4},
     year = {2021},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2021_41_4_a7/}
}
TY  - JOUR
AU  - Dong, Aijun
AU  - Li, Tong
TI  - Neighbor Product Distinguishing Total Colorings of Planar Graphs with Maximum Degree at least Ten
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2021
SP  - 981
EP  - 999
VL  - 41
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2021_41_4_a7/
LA  - en
ID  - DMGT_2021_41_4_a7
ER  - 
%0 Journal Article
%A Dong, Aijun
%A Li, Tong
%T Neighbor Product Distinguishing Total Colorings of Planar Graphs with Maximum Degree at least Ten
%J Discussiones Mathematicae. Graph Theory
%D 2021
%P 981-999
%V 41
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2021_41_4_a7/
%G en
%F DMGT_2021_41_4_a7
Dong, Aijun; Li, Tong. Neighbor Product Distinguishing Total Colorings of Planar Graphs with Maximum Degree at least Ten. Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 4, pp. 981-999. http://geodesic.mathdoc.fr/item/DMGT_2021_41_4_a7/

[1] N. Alon, Combinatorial Nullstellensatz, Combin. Probab. Comput. 8 (1999) 7–29. https://doi.org/10.1017/S0963548398003411

[2] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (North-Holland, New York, 1976).

[3] X.E. Chen, On the adjacent vertex distinguishing total coloring numbers of graphs with Δ= 3, Discrete Math. 308 (2008) 4003–4007. https://doi.org/10.1016/j.disc.2007.07.091

[4] X.H. Cheng, G.H. Wang and J.L. Wu, The adjacent vertex distinguishing total chromatic numbers of planar graphs Δ = 10, J. Comb. Optim. 34 (2017) 383–397. https://doi.org/10.1007/s10878-016-9995-x

[5] X.H. Cheng and J.L. Wu, The adjacent vertex distinguishing total choosability of planar graphs with maximum degree at least eleven, J. Comb. Optim. 35 (2018) 1–13. https://doi.org/10.1007/s10878-017-0149-6

[6] L.H. Ding, G.H. Wang and G.Y. Yan, Neighbor sum distinguishing total colorings via the Combinatorial Nullstellensatz, Sci. China Math. 57 (2014) 1875–1882. https://doi.org/10.1007/s11425-014-4796-0

[7] L.H. Ding, G.H. Wang, J.L. Wu and J.G. Yu, Neighbor sum (set) distinguishing total choosability via the Combinatorial Nullstellensatz, Graphs Combin. 33 (2017) 885–900. https://doi.org/10.1007/s00373-017-1806-3

[8] S. Ge, J.G. Li and C.Q. Xu, Neighbor sum distinguishing total coloring of planar graphs without 5 -cycles, Theoret. Comput. Sci. 689 (2017) 169–175. https://doi.org/10.1016/j.tcs.2017.05.037

[9] D.J. Huang and W.F. Wang, Adjacent vertex distinguishing total coloring of planar graphs with large maximum degree, Sci. Sin. Math. 42 (2012) 151–164 (in Chinese). https://doi.org/10.1360/012011-359

[10] T. Li, C.Q. Qu, G.H. Wang and X.W. Yu, Neighbor product distinguishing total colorings, J. Comb. Optim. 33 (2017) 237–253. https://doi.org/10.1007/s10878-015-9952-0

[11] H.L. Li, B.Q. Liu and G.H. Wang, Neighbor sum distinguishing total colorings of K 4-minor free graphs, Front. Math. China 8 (2013) 1351–1366. https://doi.org/10.1007/s11464-013-0322-x

[12] H.L. Li, L.H. Ding, B.Q. Liu and G.H. Wang, Neighbor sum distinguishing total colorings of planar graphs, J. Comb. Optim. 30 (2015) 675–688. https://doi.org/10.1007/s10878-013-9660-6

[13] Y. Lu, J.A. Li, R. Luo and Z.K. Miao, Adjacent vertex distinguishing total coloring of graphs with maximum degree 4, Discrete Math. 340 (2017) 119–123. https://doi.org/10.1016/j.disc.2016.07.011

[14] Y. Lu, C.D. Xu and Z.K. Miao, Neighbor sum distinguishing list total coloring of subcubic graphs, J. Comb. Optim. 35 (2018) 778–793. https://doi.org/10.1007/s10878-017-0239-5

[15] C.Q. Qu, G.H. Wang, J.L. Wu and X.W. Yu, On the neighbor sum distinguishing total coloring of planar graphs, Theoret. Comput. Sci. 609 (2016) 162–170. https://doi.org/10.1016/j.tcs.2015.09.017

[16] H.J. Song and C.Q. Xu, Neighbor sum distinguishing total coloring of planar graphs without 4-cycles, J. Comb. Optim. 34 (2017) 1147–1158. https://doi.org/10.1007/s10878-017-0137-x

[17] L. Sun, X.H. Cheng and J.L. Wu, The adjacent vertex distinguishing total coloring of planar graphs without adjacent 4 -cycles, J. Comb. Optim. 33 (2017) 779–790. https://doi.org/10.1007/s10878-016-0004-1

[18] H.Y. Wang, On the adjacent vertex-distinguishing total chromatic numbers of the graphs with (G) = 3, J. Comb. Optim. 14 (2007) 87–109. https://doi.org/10.1007/s10878-006-9038-0

[19] H.Y. Wang, The adjacent vertex-distinguishing total chromatic number of 1-tree, Ars Combin. 91 (2009) 183–192.

[20] Y.Q. Wang and W.F. Wang, Adjacent vertex distinguishing total colorings of outer-planar graphs, J. Comb. Optim. 19 (2010) 123–133. https://doi.org/10.1007/s10878-008-9165-x

[21] W.F. Wang and P. Wang, On adjacent-vertex-distinguishing total coloring of K4-minor free graphs, Sci. China Ser. A Math. 39 (2009) 1462–1472 (in Chinese). https://doi.org/10.1360/za2009-39-12-1462

[22] W F. Wang and Y.Q. Wang, Adjacent vertex distinguishing total coloring of graphs with lower average degree, Taiwanese J. Math. 12 (2008) 979–990. https://doi.org/10.11650/twjm/1500404991

[23] W.F. Wang and D.J. Huang, The adjacent vertex distinguishing total coloring of planar graphs, J. Comb. Optim. 27 (2014) 379–396. https://doi.org/10.1007/s10878-012-9527-2

[24] D.L. Yang, L. Sun, X.W. Yu, J.L. Wu and S. Zhou, Neighbor sum distinguishing total chromatic number of planar graphs with maximum degree 10, Appl. Math. Comput. 314 (2017) 456–468. https://doi.org/10.1016/j.amc.2017.06.002

[25] Z.F. Zhang, X.E. Chen, J.W. Li, B. Yao, X.Z. Lu and J.F. Wang, On adjacent-vertex-distinguishing total coloring of graphs, Sci. China Math. 48 (2005) 289–299. https://doi.org/10.1360/03ys0207