Neighbor sum distinguishing total coloring of 2-degenerate graphs

被引:0
作者
Jingjing Yao
Xiaowei Yu
Guanghui Wang
Changqing Xu
机构
[1] Hebei University of Technology,School of Science
[2] Shandong University,School of Mathematics
来源
Journal of Combinatorial Optimization | 2017年 / 34卷
关键词
Neighbor sum distinguishing total coloring; 2-Degenerate graph; Combinatorial Nullstellensatz; Lexicographic order;
D O I
暂无
中图分类号
学科分类号
摘要
A proper k-total coloring of a graph G is a mapping from V(G)∪E(G)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$V(G)\cup E(G)$$\end{document} to {1,2,…,k}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\{1,2,\ldots ,k\}$$\end{document} such that no two adjacent or incident elements in V(G)∪E(G)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$V(G)\cup E(G)$$\end{document} receive the same color. Let f(v) denote the sum of the colors on the edges incident with v and the color on vertex v. A proper k-total coloring of G is called neighbor sum distinguishing if f(u)≠f(v)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$f(u)\ne f(v)$$\end{document} for each edge uv∈E(G)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$uv\in E(G)$$\end{document}. Let χΣ′′(G)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\chi ''_{\Sigma }(G)$$\end{document} denote the smallest integer k in such a coloring of G. Pilśniak and Woźniak conjectured that for any graph G, χΣ′′(G)≤Δ(G)+3\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\chi ''_{\Sigma }(G)\le \Delta (G)+3$$\end{document}. In this paper, we show that if G is a 2-degenerate graph, then χΣ′′(G)≤Δ(G)+3\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\chi ''_{\Sigma }(G)\le \Delta (G)+3$$\end{document}; Moreover, if Δ(G)≥5\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Delta (G)\ge 5$$\end{document} then χΣ′′(G)≤Δ(G)+2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\chi ''_{\Sigma }(G)\le \Delta (G)+2$$\end{document}.
引用
收藏
页码:64 / 70
页数:6
相关论文
共 29 条
[1]  
Alon N(1999)Combinatorial Nullstellensatz Comb Probab Comput 8 7-29
[2]  
Ding L(2014)Neighbor sum distinguishing total colorings via the Combinatorial Nullstellensatz Sci China Math 57 1875-1882
[3]  
Wang G(2014)Neighbor sum distinguishing total coloring of graphs with bounded maximum average degree Acta Math Sin 30 703-709
[4]  
Yan G(2015)Neighbor sum distinguishing total colorings of planar graphs J Comb Optim 30 675-688
[5]  
Dong A(2013)Neighbor sum distinguishing total colorings of Front Math China 8 1351-1366
[6]  
Wang G(2016)-minor free graphs Theor Comp Sci 609 162-170
[7]  
Li H(2016)On the neighbor sum distinguishing total coloring of planar graphs J Comb Optim 31 874-880
[8]  
Ding L(2009)Adjacent vertex distinguishing edge coloring of 2-degenerate graphs Sci China Ser A 39 1462-1472
[9]  
Liu B(2005)On adjacent-vertex-distinguishing total coloring of Sci China Ser A 48 289-299
[10]  
Wang G(undefined)-minor free graphs undefined undefined undefined-undefined