Article in press
Authors:
Hsin-Hao Lai
Department of Mathematics, National Kaohsiung Normal University
email: hsinhaolai@mail.nknu.edu.tw
Yi-Hsuan Huang
Department of Mathematics, National Kaohsiung Normal University
email: joyce882288@yahoo.com.tw
Yu-Jhan Su
Department of Mathematics, National Kaohsiung Normal University
email: d0a3n0@yahoo.com.tw
Title:
Proper additive choice number of planar graphs
PDFSource:
Discussiones Mathematicae Graph Theory
Received: 2024-12-28 , Revised: 2025-06-22 , Accepted: 2025-07-03 , Available online: 2025-09-10 , https://doi.org/10.7151/dmgt.2601
Abstract:
A proper additive coloring of a graph $G$ is a labeling of its vertices
with positive integers such that, for every pair of adjacent vertices, the
assigned integers are distinct and the sums of integers assigned to their
neighbors are different. The proper additive choice number of $G$ is the
least integer $k$ such that, whenever each vertex is given a list of at least
$k$ available integers, a proper additive coloring can be chosen from the lists.
In this paper, we introduce some applications of Combinatorial Nullstellensatz
in the study of proper additive coloring and present upper bounds on the
proper additive choice number of planar graphs.
Keywords:
proper additive coloring, proper additive chromatic number, proper additive choice number, planar graph, Combinatorial Nullstellensatz, discharging method
References:
- A. Ahadi and A. Dehghan, The inapproximability for the $(0,1)$-additive number, Discrete Math. Theor. Comput. Sci. 17 (2016) 217–226.
https://doi.org/10.46298/dmtcs.2145 - S. Akbari, M. Ghanbari, R. Manaviyat and S. Zare, On the lucky choice number of graphs, Graphs Combin. 29 (2013) 157–163.
https://doi.org/10.1007/s00373-011-1112-4 - N. Alon, Combinatorial nullstellensatz, Combin. Probab. Comput. 8 (1999) 7–29.
https://doi.org/10.1017/S0963548398003411 - N. Alon and M. Tarsi, Colorings and orientations of graphs, Combinatorica 12 (1992) 125–134.
https://doi.org/10.1007/BF01204715 - Z. An, S. Tian and C. Jin, Proper additive coloring of special graphs, in: 2020 International Conference on Computer Science and Management Technology, Shangai, China, (IEEE 2020) 39–43.
https://doi.org/10.1109/ICCSMT51754.2020.00015 - M. Axenovich, J. Harant, J. Przybyło, R. Soták, M. Voigt and J. Weidelich, A note on adjacent vertex distinguishing colorings of graphs, Discrete Appl. Math. 205 (2016) 1–7.
https://doi.org/10.1016/j.dam.2015.12.005 - T. Bartnicki, B. Bosek, S. Czerwiński, J. Grytczuk, G. Matecki and W. Żelazny, Additive coloring of planar graphs, Graphs Combin. 30 (2014) 1087–1098.
https://doi.org/10.1007/s00373-013-1331-y - M. Bonamy, B. Lévêque and A. Pinlou, $2$-distance coloring of sparse graphs, J. Graph Theory 77 (2014) 190–218.
https://doi.org/10.1002/jgt.21782 - A. Brandt, S. Jahanbekam and J. White, Additive list coloring of planar graphs with given girth, Discuss. Math. Graph Theory 40 (2020) 855–873.
https://doi.org/10.7151/dmgt.2156 - A. Brandt, N. Tenpas and C.R. Yerger, Planar graphs with girth $20$ are additively $3$-choosable, Discrete Appl. Math. 277 (2020) 14–21.
https://doi.org/10.1016/j.dam.2019.08.021 - G. Chartrand, F. Okamoto and P. Zhang, The sigma chromatic number of a graph, Graphs Combin. 26 (2010) 755–773.
https://doi.org/10.1007/s00373-010-0952-7 - D.W. Cranston and R. Škrekovski, Sufficient sparseness conditions for $G^2$ to be $(\Delta+1)$-choosable, when $\Delta \geqslant5$, Discrete Appl. Math. 162 (2014) 167–176.
https://doi.org/10.1016/j.dam.2013.08.025 - D.W. Cranston and D.B. West, An introduction to the discharging method via graph coloring, Discrete Math. 340 (2017) 766–793.
https://doi.org/10.1016/j.disc.2016.11.022 - S. Czerwiński, J. Grytczuk and W. Żelazny, Lucky labelings of graphs, Inform. Process. Lett. 109 (2009) 1078–1081.
https://doi.org/10.1016/j.ipl.2009.05.011 - J. van den Heuvel and S. McGuinness, Coloring the square of a planar graph, J. Graph Theory 42 (2003) 110–124.
https://doi.org/10.1002/jgt.10077 - H.-H. Lai and K.-W. Lih, A note on additive choice number of planar graphs, Discrete Appl. Math. 321 (2022) 357–359.
https://doi.org/10.1016/j.dam.2022.07.010 - W. Ruksasakchai and T. Wang, List strong edge coloring of some classes of graphs, Australas. J. Combin. 68 (2017) 106–117.
- T.V. Sateesh Kumar and S. Meenakshi, Proper lucky labeling of graph, in: Proceedings of First International Conference on Mathematical Modeling and Computational Science, S.L. Peng, R.X. Hao and S. Pal (Ed(s)), (Springer, Singapore 2021) 341–351.
https://doi.org/10.1007/978-981-33-4389-4_31
Close