Geodesic
Additive List Coloring of Planar Graphs with Given Girth
Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 3, pp. 855-873.

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

An additive coloring of a graph G is a labeling of the vertices of G from 1, 2, . . ., k such that two adjacent vertices have distinct sums of labels on their neighbors. The least integer k for which a graph G has an additive coloring is called the additive coloring number of G, denoted χΣ (G). Additive coloring is also studied under the names lucky labeling and open distinguishing. In this paper, we improve the current bounds on the additive coloring number for particular classes of graphs by proving results for a list version of additive coloring. We apply the discharging method and the Combinatorial Nullstellensatz to show that every planar graph G with girth at least 5 has χΣ (G) ≤ 19, and for girth at least 6, 7, and 26, χΣ (G) is at most 9, 8, and 3, respectively. In 2009, Czerwiński, Grytczuk, and Żelazny conjectured that χΣ (G) ≤ χ(G), where χ(G) is the chromatic number of G. Our result for the class of non-bipartite planar graphs of girth at least 26 is best possible and affirms the conjecture for this class of graphs.
Keywords: lucky labeling, additive coloring, reducible configuration, discharging method, Combinatorial Nullstellensatz 
@article{DMGT_2020_40_3_a10,
     author = {Brandt, Axel and Jahanbekam, Sogol and White, Jennifer},
     title = {Additive {List} {Coloring} of {Planar} {Graphs} with {Given} {Girth}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {855--873},
     publisher = {mathdoc},
     volume = {40},
     number = {3},
     year = {2020},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2020_40_3_a10/}
}
TY  - JOUR
AU  - Brandt, Axel
AU  - Jahanbekam, Sogol
AU  - White, Jennifer
TI  - Additive List Coloring of Planar Graphs with Given Girth
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2020
SP  - 855
EP  - 873
VL  - 40
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2020_40_3_a10/
LA  - en
ID  - DMGT_2020_40_3_a10
ER  - 
%0 Journal Article
%A Brandt, Axel
%A Jahanbekam, Sogol
%A White, Jennifer
%T Additive List Coloring of Planar Graphs with Given Girth
%J Discussiones Mathematicae. Graph Theory
%D 2020
%P 855-873
%V 40
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2020_40_3_a10/
%G en
%F DMGT_2020_40_3_a10
Brandt, Axel; Jahanbekam, Sogol; White, Jennifer. Additive List Coloring of Planar Graphs with Given Girth. Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 3, pp. 855-873. http://geodesic.mathdoc.fr/item/DMGT_2020_40_3_a10/

[1] A. Ahadi, A. Dehghan, M. Kazemi and E. Mollaahmadi, Computation of lucky number of planar graphs is NP-hard, Inform. Process. Lett. 112 (2012) 109–112. doi:10.1016/j.ipl.2011.11.002

[2] A. Ahadi and A. Dehghan, The inapproximability for the (0, 1)-additive number, Discrete Math. Theor. Comput. Sci. 17 (2016) 217–226.

[3] S. Akbari, M. Ghanbari, R. Manaviyat and S. Zare, On the lucky choice number of graphs, Graphs Combin. 29 (2013) 157–163. doi:10.1007/s00373-011-1112-4

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

[5] M. Axenovich, J. Harant, J. Przyby lo, R. Soták, M. Voigt and J. Weidelich, A note on adjacent vertex distinguishing colorings of graphs, Discrete Appl. Math. 205 (2016) 1–7. doi:10.1016/j.dam.2015.12.005

[6] 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. doi:10.1007/s00373-013-1331-y

[7] A. Brandt, M. Ferrara, M. Kumbhat, S. Loeb, D. Stolee and M. Yancey, I,F-partitions of sparse graphs, European J. Combin. 57 (2016) 1–12. doi:10.1016/j.ejc.2016.03.003

[8] Y. Bu, D. Cranston, M. Montassier, A. Raspaud and W. Wang, Star coloring of sparse graphs, J. Graph Theory 62 (2009) 201–219. doi:10.1002/jgt.20392

[9] G. Chartrand, F. Okamoto and P. Zhang, The sigma chromatic number of a graph, Graphs Combin. 26 (2010) 755–773. doi:10.1007/s00373-010-0952-7

[10] D.W. Cranston and D.B. West, An introduction to the discharging method via graph coloring, Discrete Math. 340 (2017) 766–793. doi:10.1016/j.disc.2016.11.022

[11] S. Czerwiński, J. Grytczuk and W. Żelazny, Lucky labelings of graphs, Inform. Process. Lett. 109 (2009) 1078–1081. doi:10.1016/j.ipl.2009.05.011

[12] A. Dehghan, M. Sadeghi and A. Ahadi, The complexity of the sigma chromatic number of cubic graphs, (2014). arXiv:math.CO/1403.6288v1

[13] A. Dehghan, M. Sadeghi and A. Ahadi, Algorithmic complexity of proper labeling problems, Theoret. Comput. Sci. 495 (2013) 25–36. doi:10.1016/j.tcs.2013.05.027

[14] H. Grötzsch, Zur Theorie der diskreten Gebilde. VII. Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg. Math.-Nat. Reihe 8 (1958/1959) 109–120.

[15] M. Kalkowski, M. Karoński and F. Pfender, Vertex-coloring edge-weightings: towards the 1-2-3-conjecture, J. Combin. Theory Ser. B 100 (2010) 347–349. doi:10.1016/j.jctb.2009.06.002

[16] M. Karoński, T. Luczak and A. Thomason, Edge weights and vertex colours, J. Combin. Theory Ser. B 91 (2004) 151–157. doi:10.1016/j.jctb.2003.12.001

[17] B. Seamone, The 1-2-3 conjecture and related problems: a survey (2012). arXiv:math.CO/1211.5122

[18] B. Seamone, Derived Colourings of Graphs (PhD Thesis, Carleton University, 2012).

[19] R. Steinberg and C.A. Tovey, Planar Ramsey numbers, J. Combin. Theory Ser. B 59 (1993) 288–296. doi:10.1006/jctb.1993.1070

[20] C. Thomassen, A short list color proof of Grötzsch’s theorem, J. Combin. Theory Ser. B 88 (2003) 189–192. doi:10.1016/S0095-8956(03)00029-7

[21] D.B. West, Introduction to Graph Theory (Prentice Hall, Inc., Upper Saddle River, NJ, 1996).