A note on the neighbor sum distinguishing total coloring of planar graphs

被引:12
作者
Song, Hong Jie [1 ]
Pan, Wen Hua [1 ]
Gong, Xiang Nan [1 ]
Xu, Chang Qing [1 ]
机构
[1] Hebei Univ Technol, Sch Sci, Tianjin 300401, Peoples R China
基金
中国国家自然科学基金;
关键词
Neighbor sum distinguishing total coloring; Combinatorial Nullstellensatz; Planar graph; COMBINATORIAL NULLSTELLENSATZ;
D O I
10.1016/j.tcs.2016.06.007
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
Let G = (V (G), E(G)) be a graph and phi be a proper total k-coloring of G. Let f (v) denote the sum of the color on a vertex v and colors on all the edges incident with v. phi is neighbor sum distinguishing if f (u) not equal f (v) for each edge uv is an element of E(G). The smallest integer k for which such a coloring of G exists is the neighbor sum distinguishing total chromatic number and denoted by chi ''(Sigma)(G). Pilsniak and Wozniak conjectured that for any simple graph with maximum degree Delta(G), chi ''(Sigma)(G) <= Delta(G) + 3. It is known that for any simple planar graph, chi ''(Sigma)(G) <= max{Delta(G) + 3,14) and chi ''(Sigma)(G) <= max{Delta(G) + 2,16). In this paper, by using the famous Combinatorial Nullstellensatz, we show that for any simple planar graph, chi ''(Sigma)(G) <= max{Delta(G) 2,14). The bound Delta(G) + 2 is sharp. (C) 2016 Elsevier B.V. All rights reserved.
引用
收藏
页码:125 / 129
页数:5
相关论文
共 15 条
  • [1] Combinatorial Nullstellensatz
    Alon, N
    [J]. COMBINATORICS PROBABILITY & COMPUTING, 1999, 8 (1-2) : 7 - 29
  • [2] Bondy J., 2008, GRADUATE TEXTS MATH
  • [3] Neighbor sum distinguishing total colorings of planar graphs with maximum degree Δ
    Cheng, Xiaohan
    Huang, Danjun
    Wang, Guanghui
    Wu, Jianliang
    [J]. DISCRETE APPLIED MATHEMATICS, 2015, 190 : 34 - 41
  • [4] Neighbor sum distinguishing total colorings via the Combinatorial Nullstellensatz
    Ding LaiHao
    Wang GuangHui
    Yan GuiYing
    [J]. SCIENCE CHINA-MATHEMATICS, 2014, 57 (09) : 1875 - 1882
  • [5] Neighbor sum distinguishing total colorings of planar graphs
    Li, Hualong
    Ding, Laihao
    Liu, Bingqiang
    Wang, Guanghui
    [J]. JOURNAL OF COMBINATORIAL OPTIMIZATION, 2015, 30 (03) : 675 - 688
  • [6] Neighbor sum distinguishing total colorings of K 4-minor free graphs
    Li, Hualong
    Liu, Bingqiang
    Wang, Guanghui
    [J]. FRONTIERS OF MATHEMATICS IN CHINA, 2013, 8 (06) : 1351 - 1366
  • [7] Pilsniak M., 2013, GRAPHS COMBIN
  • [9] Qu C., 2015, J COMB OPTIM
  • [10] On the neighbor sum distinguishing total coloring of planar graphs
    Qu, Cunquan
    Wang, Guanghui
    Wu, Jianliang
    Yu, Xiaowei
    [J]. THEORETICAL COMPUTER SCIENCE, 2016, 609 : 162 - 170