A neighbor sum distinguishing (NSD) total coloring $ \phi $ of $ G $ is a proper total coloring such that $ \sum_{z\in E_{G}(u)\cup\{u\}}\phi(z)\neq\sum_{z\in E_{G}(v)\cup\{v\}}\phi(z) $ for each edge $ uv\in E(G) $. Pilśniak and Woźniak asserted that each graph with a maximum degree $ \Delta $ admits an NSD total $ (\Delta+3) $-coloring in 2015. In this paper, we prove that the list version of this conjecture holds for any IC-planar graph with $ \Delta\geq10 $ but without five cycles by applying the discharging method, which improves the result of Zhang (NSD list total coloring of IC-planar graphs without five cycles).
Citation: Fugang Chao, Donghan Zhang. Neighbor sum distinguishing total choice number of IC-planar graphs with restrictive conditions[J]. AIMS Mathematics, 2023, 8(6): 13637-13646. doi: 10.3934/math.2023692
A neighbor sum distinguishing (NSD) total coloring $ \phi $ of $ G $ is a proper total coloring such that $ \sum_{z\in E_{G}(u)\cup\{u\}}\phi(z)\neq\sum_{z\in E_{G}(v)\cup\{v\}}\phi(z) $ for each edge $ uv\in E(G) $. Pilśniak and Woźniak asserted that each graph with a maximum degree $ \Delta $ admits an NSD total $ (\Delta+3) $-coloring in 2015. In this paper, we prove that the list version of this conjecture holds for any IC-planar graph with $ \Delta\geq10 $ but without five cycles by applying the discharging method, which improves the result of Zhang (NSD list total coloring of IC-planar graphs without five cycles).
| [1] | J. A. Bondy, U. S. R. Murty, Graph theory, Graduate Texts in Mathematics, London: Springer, 2008. |
| [2] |
M. Pilśniak, M. Woźniak, On the total-neighbor-distinguishing index by sums, Graph. Combinator., 31 (2015), 771–782. https://doi.org/10.1007/s00373-013-1399-4 doi: 10.1007/s00373-013-1399-4
|
| [3] |
D. Yang, L. Sun, X. Yu, J. Wu, 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 doi: 10.1016/j.amc.2017.06.002
|
| [4] |
S. Ge, J. Li, C. Xu, Neighbor sum distinguishing total coloring of planar graphs without 5-cycles, Theor. Comput. Sci., 689 (2017), 169–175. https://doi.org/10.1016/j.tcs.2017.05.037 doi: 10.1016/j.tcs.2017.05.037
|
| [5] | M. O. Alberson, Chromatic number, independent ratio, and crossing number, Ars Math. Contemp., 1 (2008), 1–6. https://doi.org/10.26493/1855-3974.10.2d0 |
| [6] |
D. Zhang, C. Li, F. Chao, On the total neighbor sum distinguishing index of IC-planar graphs, Symmetry, 13 (2021), 1787. https://doi.org/10.3390/sym13101787 doi: 10.3390/sym13101787
|
| [7] |
W. Song, Y. Duan, L. Miao, Neighbor sum distinguishing total coloring of triangle free IC-planar graphs, Acta Math. Sin. Engl. Ser., 36 (2020), 292–304. https://doi.org/10.1007/s10114-020-9189-4 doi: 10.1007/s10114-020-9189-4
|
| [8] |
C. Song, X. Jin, C. Xu, Neighbor sum distinguishing total coloring of IC-planar graphs with short cycle restrictions, Discrete Appl. Math., 279 (2020), 202–209. https://doi.org/10.1016/j.dam.2019.12.023 doi: 10.1016/j.dam.2019.12.023
|
| [9] |
Y. Lu, C. Xu, Z. 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 doi: 10.1007/s10878-017-0239-5
|
| [10] |
D. Zhang, Y. Lu, S. Zhang, Neighbor Sum Distinguishing Total Choosability of Cubic Graphs, Graph. Combinator., 36 (2020), 1545–1562. https://doi.org/10.1007/s00373-020-02196-3 doi: 10.1007/s00373-020-02196-3
|
| [11] |
C. Qu, G. Wang, G. Yan, X. Yu, Neighbor sum distinguishing total choosability of planar graphs, J. Comb. Optim., 32 (2016), 906–916. https://doi.org/10.1007/s10878-015-9911-9 doi: 10.1007/s10878-015-9911-9
|
| [12] |
J. Wang, J. Cai, B. Qiu, Neighbor sum distinguishing total choosability of planar graphs without adjacent triangles, Theor. Comput. Sci., 661 (2017), 1–7. https://doi.org/10.1016/j.tcs.2016.11.003 doi: 10.1016/j.tcs.2016.11.003
|
| [13] |
W. Song, L. Miao, Y. Duan, Neighbor sum distinguishing total choosability of IC-planar graphs, Discuss. Math. Graph T., 40 (2020), 331–344. https://doi.org/10.7151/dmgt.2145 doi: 10.7151/dmgt.2145
|
| [14] | D. Zhang, Neighbor sum distinguishing list total coloring of IC-planar graphs without 5-cycles, Czech. Math. J., 72 (2022), 111–124. https://articles.math.cas.cz/10.21136/CMJ.2021.0333-20 |
| [15] |
P. N. Balister, E. Győri, J. Lehel, R. H. Schelp, Adjacent vertex distinguishing edge-colorings, SIAM J. Discrete Math., 21 (2007), 237–250. https://doi.org/10.1137/S0895480102414107 doi: 10.1137/S0895480102414107
|
| [16] |
X. Chen, On the adjacent vertex distinguishing total coloring numbers of graphs with $\Delta = 3$, Discrete Math., 308 (2008), 4003–4007. https://doi.org/10.1016/j.disc.2007.07.091 doi: 10.1016/j.disc.2007.07.091
|
| [17] |
N. Alon, Combinatorial nullstellensatz, Comb. Probab. Comput., 8 (1999), 7–29. https://doi.org/10.1017/S0963548398003411 doi: 10.1017/S0963548398003411
|
| [18] |
C. Qu, L. Ding, G. Wang, G. Yan, Neighbor distinguishing total choice number of sparse graphs via the Combinatorial Nullstellensatz, Acta Math. Appl. Sin. Engl. Ser., 32 (2016), 537–548. https://doi.org/10.1007/s10255-016-0583-8 doi: 10.1007/s10255-016-0583-8
|
Figures(1)
Fugang Chao, Donghan Zhang. Neighbor sum distinguishing total choice number of IC-planar graphs with restrictive conditions[J]. AIMS Mathematics, 2023, 8(6): 13637-13646. doi: 10.3934/math.2023692
DownLoad: