Neighbor sum distinguishing total choice number of graphs with bounded maximum average degree

doi:10.3969/j.issn.1000-5641.2022.01.002

Abstract

Abstract:

This paper explores the neighbor sum distinguishing list total coloring of graphs $G$ with maximum degree $\varDelta \left( G \right) \geqslant 8$ and maximum average degree ${\rm{mad}}\left( G \right) < \frac{{14}}{3}$ . By applications of the Combinatorial Nullstellensatz and discharge method, moreover, it is shown that the neighbor sum distinguishing total choice number of the graphs does not exceed $\varDelta \left( G \right) + 3$ .

Key words: Combinatorial Nullstellensatz, neighbor sum distinguishing total choice number, discharge method

CLC Number:

O157.5

Donghan ZHANG. Neighbor sum distinguishing total choice number of graphs with bounded maximum average degree[J]. Journal of East China Normal University(Natural Science), 2022, 2022(1): 10-16.

References 17

1	BONDY J A, MURTY U S R. Graph Theory with Applications [M]. New York: Macmilan Press Ltd, 1976.
2	PILŚNIAK M, WOŹNIAK M. On the total-neighbor-distinguishing index by sums. Graphs and Combinatorics, 2015, 31 (3): 771- 782. doi: 10.1007/s00373-013-1399-4
3	DONG A J, WANG G H. Neighbor sum distinguishing total colorings of graphs with bounded maximum average degree. Acta Mathematica Sinica (English Series), 2014, 30 (4): 703- 709. doi: 10.1007/s10114-014-2454-7
4	HOCQUARD H, PRZYBYŁO J. On the total neighbour sum distinguishing index of graphs with bounded maximum average degree. Journal of Combinatorial Optimization, 2020, 39, 412- 424. doi: 10.1007/s10878-019-00480-4
5	WANG J H, MA Q L, HAN X, et al. A proper total coloring distinguishing adjacent vertices by sums of planar graphs without intersecting triangles. Journal of Combinatorial Optimization, 2016, 32 (2): 626- 638. doi: 10.1007/s10878-015-9886-6
6	YANG D L, SUN L, YU X W, et al. Neighbor sum distinguishing total chromatic number of planar graphs with maximum degree 10. Applied Mathematics and Computation, 2017, 314, 456- 468. doi: 10.1016/j.amc.2017.06.002
7	QU C Q, WANG G H, WU J L, et al. On the neighbor sum distinguishing total colorings of planar graphs. Theoretical Computer Science, 2016, 609, 162- 170. doi: 10.1016/j.tcs.2015.09.017
8	SONG H J, PAN W H, GONG X N, et al. A note on the neighbor sum distinguishing total coloring of planar graphs. Theoretical Computer Science, 2016, 640, 125- 129. doi: 10.1016/j.tcs.2016.06.007
9	SONG W Y, DUAN Y Y, MIAO L Y. Neighbor sum distinguishing total coloring of IC-planar graphs. Discrete Mathematics, 2020, 343 (8): 111918. doi: 10.1016/j.disc.2020.111918
10	HAN M M, LU Y, LUO R, et al. Neighbor sum distinguishing total coloring of graphs with bounded treewidth. Journal of Combinatorial Optimization, 2018, 36, 23- 34. doi: 10.1007/s10878-018-0271-0
11	于筱蔚. 图的点可区别染色和标号 [D]. 济南: 山东大学, 2018.
12	QU C Q, DING L H, WANG G H, et al. Neighbor distinguishing total choice number of sparse graphs via the Combinatorial Nullstellensatz. Acta Mathematica Sinica (English Series), 2016, 32 (2): 537- 548. doi: 10.1007/s10255-016-0583-8
13	LU Y, XU C D, MIAO Z K. Neighbor sum distinguishing list total coloring of subcubic graphs. Journal of Combinatorial Optimization, 2018, 35, 778- 793. doi: 10.1007/s10878-017-0239-5
14	SUN L, YU G L, LI X. Neighbor sum distinguishing total choosability of 1-planar graphs with maximum degree at least 24. Discrete Mathematics, 2021, 344 (1): 112190. doi: 10.1016/j.disc.2020.112190
15	ZHANG D H, LU Y, ZHANG S G. Neighbor sum distinguishing total choice number of planar graphs without 6-cycles. Acta Mathematica Sinica (English Series), 2020, 36 (12): 1417- 1428. doi: 10.1007/s10114-020-0144-1
16	ZHANG D H, LU Y, ZHANG S G. Neighbor sum distinguishing total choosability of cubic graphs. Graphs and Combinatorics, 2020, 36, 1417- 1428.
17	ALON N. Combinatorial Nullstellensatz. Combinatorics Probability & Computing, 1999, (8): 7- 29.

[1]	HAN Xin-yin, YAO Min, ZUO Lian-cui, ZHOU Wei-na. (d,1)-total labeling of lexicographic products of some classes of graphs [J]. Journal of East China Normal University(Natural Sc, 2019, 2019(3): 35-41.
[2]	ZHANG Yi, LIU Zhi-qiang, ZOU Si-si, WEN Li-min. Estimation of loss reserves based on a hierarchical bayesian model [J]. Journal of East China Normal University(Natural Sc, 2019, 2019(1): 13-23.
[3]	CHEN Xiao-feng, WANG Yi-qiao. L(2, 1)-labelling of Halin graphs with a maximum degree of seven [J]. Journal of East China Normal University(Natural Sc, 2019, 2019(1): 39-47,57.
[4]	SHI Xue-qin, TANG Xia, WEI Yu-mei, WANG Jian. Study and investigation of Lejeuneaceae species diversity in Anhui Province [J]. Journal of East China Normal University(Natural Sc, 2018, 2018(4): 138-146.
[5]	ZHANG Quan-rui, LIU Jian-cheng. L² harmonic 2-forms on a hypersurface in Euclidean space [J]. Journal of East China Normal University(Natural Sc, 2018, 2018(3): 38-45.
[6]	SU Ya-pan, PAN Hai-lin, ZHAO Zhen-jie, YUAN Meng-ping. Influence of dipolar magnetic interaction on the LDGMI effect of Fe-based nanocrystalline ribbons [J]. Journal of East China Normal University(Natural Sc, 2018, 2018(3): 129-135,156.
[7]	SUN Hui, YAO Bing. Exploring equivalent definitions of eulerian graphs [J]. Journal of East China Normal University(Natural Sc, 2018, 2018(2): 23-30,40.
[8]	CHEN Shao-jun, LI Xiao-tao, ZHENG Jun-hua. Research progress of the target proteins by proteasome activator REGγ in human cancers [J]. Journal of East China Normal University(Natural Sc, 2018, 2018(2): 125-130,159.
[9]	ZHOU Xiao-xiao, BI Chun-juan, WANG Meng, ZHOU Ya, CHEN Zhen-lou. Pollution effects of atmospheric deposition on heavy metals in leafy vegetables and its health risks [J]. Journal of East China Normal University(Natural Sc, 2018, 2018(2): 141-150.
[10]	LI Yi-chun, SUN Hui, YAO Bing. Edge-magic even-gracefulness of several kinds of spread network models [J]. Journal of East China Normal University(Natural Sc, 2018, 2018(1): 11-16,23.
[11]	DONG Yong-peng, WANG Qian-ru, MA Jiao-jiao. A stability theorem for solutions of general time interval multidimensional BSDEs with uniformly continuous generators [J]. Journal of East China Normal University(Natural Sc, 2018, 2018(1): 24-34,49.
[12]	YANG Yan-yan, WEI Wen-long, HUANG Zhi-gang. Meromorphic solutions of some type of system of differential and difference equations [J]. Journal of East China Normal University(Natural Sc, 2018, 2018(1): 50-58.
[13]	MA Fei, YAO Bing. One scale-free network model based on two different preferential attachment probabilities [J]. Journal of East China Normal University(Natural Sc, 2017, 2017(6): 42-49.
[14]	MA Hua, JIANG Xue-Zhong. In consideration of tidal condition to improve optical inversion algorithm on total suspended matters concentration according to in situ measurement in the Yangtze Estuary [J]. Journal of East China Normal University(Natural Sc, 2016, 2016(3): 146-155.
[15]	XU Yang. List improper coloring of graphs of nonnegative characteristic [J]. Journal of East China Normal University(Natural Sc, 2016, 2016(2): 51-55.