Authors: L.-Y. Miao, W.-Y. Song Title: Neighbor sum distinguishing total choosability of IC-planar graphs Source: Discussiones Mathematicae Graph Theory Received 30.06.2017, Revised 21.03.2018, Accepted 21.03.2018, doi: 10.7151/dmgt.2145 | |
Abstract: 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 | |
Links: |