Geodesic
Neighbor Sum Distinguishing Total Choosability of IC-Planar Graphs
Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 1, pp. 331-344.

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

Two distinct crossings are independent if the end-vertices of the crossed pair of edges are mutually different. If a graph G has a drawing in the plane such that every two crossings are independent, then we call G a plane graph with independent crossings or IC-planar graph for short. A proper total-k-coloring of a graph G is a mapping c : V (G) ∪ E(G) →{ 1, 2, . . ., k } such that any two adjacent elements in V (G) ∪ E(G) receive different colors. Let Σ_c (v) denote the sum of the color of a vertex v and the colors of all incident edges of v. A total-k-neighbor sum distinguishing-coloring of G is a total-k-coloring of G such that for each edge uv ∈ E(G), Σ_c (u) Σ_c (v). The least number k needed for such a coloring of G is the neighbor sum distinguishing total chromatic number, denoted by χ_Σ^” (G). In this paper, it is proved that if G is an IC-planar graph with maximum degree Δ (G), then ch_Σ^” (G) ≤max{Δ (G)+3, 17 }, where ch_Σ^” (G) is the neighbor sum distinguishing total choosability of G.
Keywords: neighbor sum distinguishing total choosability, maximum degree, IC-planar graph, Combinatorial Nullstellensatz 
@article{DMGT_2020_40_1_a22,
     author = {Song, Wen-Yao and Miao, Lian-Ying and Duan, Yuan-Yuan},
     title = {Neighbor {Sum} {Distinguishing} {Total} {Choosability} of {IC-Planar} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {331--344},
     publisher = {mathdoc},
     volume = {40},
     number = {1},
     year = {2020},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2020_40_1_a22/}
}
TY  - JOUR
AU  - Song, Wen-Yao
AU  - Miao, Lian-Ying
AU  - Duan, Yuan-Yuan
TI  - Neighbor Sum Distinguishing Total Choosability of IC-Planar Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2020
SP  - 331
EP  - 344
VL  - 40
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2020_40_1_a22/
LA  - en
ID  - DMGT_2020_40_1_a22
ER  - 
%0 Journal Article
%A Song, Wen-Yao
%A Miao, Lian-Ying
%A Duan, Yuan-Yuan
%T Neighbor Sum Distinguishing Total Choosability of IC-Planar Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2020
%P 331-344
%V 40
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2020_40_1_a22/
%G en
%F DMGT_2020_40_1_a22
Song, Wen-Yao; Miao, Lian-Ying; Duan, Yuan-Yuan. Neighbor Sum Distinguishing Total Choosability of IC-Planar Graphs. Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 1, pp. 331-344. http://geodesic.mathdoc.fr/item/DMGT_2020_40_1_a22/

[1] M.O. Albertson, Chromatic number, independence ratio, and crossing number, Ars Math. Contemp. 1 (2008) 1–6.

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

[3] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (North-Holland, New York-Amsterdam-Oxford, 1982).

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

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

[6] A. Dong and G. Wang, Neighbor sum distinguishing total colorings of graphs with bounded maximum average degree, Acta Math. Sin. (Engl. Ser.) 30 (2014) 703–709. doi:10.1007/s10114-014-2454-7

[7] D. Král and L. Stacho, Coloring plane graphs with independent crossings, J. Graph Theory 64 (2010) 184–205. doi:10.1002/jgt.20448

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

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

[10] S. Loeb, J. Przybyło and Y. Tang, Asymptotically optimal neighbor sum distinguishing total colorings of graphs, Discrete Math. 340 (2017) 58–62. doi:10.1016/j.disc.2016.08.012

[11] M. Pilśniak and M. Woźniak, On the total-neighbor-distinguishing index by sums, Graphs Combin. 31 (2015) 771–782. doi:10.1007/s00373-013-1399-4

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

[13] C. Qu, G. Wang, G. Yan and X. Yu, Neighbor sum distinguishing total choosability of planar graphs, J. Comb. Optim. 32 (2016) 906–916. doi:10.1007/s10878-015-9911-9

[14] D.E. Scheim, The number of edge 3 -colorings of a planar cubic graph as a permanent, Discrete Math. 8 (1974) 377–382. doi:10.1016/0012-365X(74)90157-5

[15] J. Wang, J. Cai and Q. Ma, Neighbor sum distinguishing total choosability of planar graphs without 4 -cycles, Discrete Appl. Math. 206 (2016) 215–219. doi:10.1016/j.dam.2016.02.003

[16] J. Yao and H. Kong, Neighbor sum distinguishing total choosability of graphs with larger maximum average degree, Ars Combin. 125 (2016) 347–360.

[17] X. Zhang and J. Wu, On edge colorings of 1 -planar graphs, Inform. Process. Lett. 111 (2011) 124–128. doi:10.1016/j.ipl.2010.11.001

[18] J. Yao, X. Yu, G. Wang and C. Xu, Neighbor sum ( set ) distinguishing total choosability of d-degenerate graphs, Graphs Combin. 32 (2016) 1611–1620. doi:10.1007/s00373-015-1646-y

[19] X. Cheng, D. Huang, G. Wang and J. Wu, Neighbor sum distinguishing total colorings of planar graphs with maximum degree, Discrete Appl. Math. 190-191 (2015) 34–41. doi:10.1016/j.dam.2015.03.013

[20] Y. Lu, M.M. Han and R. Luo, Neighbor sum distinguishing total coloring and list neighbor sum distinguishing total coloring, Discrete Appl. Math. 237 (2018) 109–115. doi:10.1016/j.dam.2017.12.001