Article ID Journal Published Year Pages File Type
6871373 Discrete Applied Mathematics 2018 10 Pages PDF
Abstract
Two distinct crossings are independent if the end-vertices of the crossed edge 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 χΣ′′(G)≤max{Δ(G)+3,11} if G is a triangle-free IC-planar graph, and χΣ′′(G)≤max{Δ(G)+3,15} if G is an IC-planar graph without adjacent triangles, where Δ(G) is the maximum degree of G.
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , , , ,