Neighbor Sum Distinguishing Total Choosability of IC-Planar Graphs

Song, Wen-Yao ; Miao, Lian-Ying ; Duan, Yuan-Yuan

Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 1, pp. 331-344

Résumé

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.

Détail

Keywords: neighbor sum distinguishing total choosability, maximum degree, IC-planar graph, Combinatorial Nullstellensatz