Neighbor sum distinguishing list total coloring of subcubic graphs

被引:0
作者
You Lu
Chuandong Xu
Zhengke Miao
机构
[1] Northwestern Polytechnical University,Department of Applied Mathematics
[2] Xidian University,School of Mathematics and Statistics
[3] Jiangsu Normal University,School of Mathematics and Statistics
来源
Journal of Combinatorial Optimization | 2018年 / 35卷
关键词
List total coloring; Neighbor sum distinguishing; Reducible configuration;
D O I
暂无
中图分类号
学科分类号
摘要
Let G=(V,E)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G=(V, E)$$\end{document} be a simple graph and denote the set of edges incident to a vertex v by E(v). The neighbor sum distinguishing (NSD) total choice number of G, denoted by chΣt(G)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathrm{ch}_{\Sigma }^{t}(G)$$\end{document}, is the smallest integer k such that, after assigning each z∈V∪E\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$z\in V\cup E$$\end{document} a set L(z) of k real numbers, G has a total coloring ϕ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\phi $$\end{document} satisfying ϕ(z)∈L(z)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\phi (z)\in L(z)$$\end{document} for each z∈V∪E\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$z\in V\cup E$$\end{document} and ∑z∈E(u)∪{u}ϕ(z)≠∑z∈E(v)∪{v}ϕ(z)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\sum _{z\in E(u)\cup \{u\}}\phi (z)\ne \sum _{z\in E(v)\cup \{v\}}\phi (z)$$\end{document} for each uv∈E\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$$\end{document}. In this paper, we propose some reducible configurations of NSD list total coloring for general graphs by applying the Combinatorial Nullstellensatz. As an application, we present that chΣt(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}$$\mathrm{ch}^{t}_{\Sigma }(G)\le \Delta (G)+3$$\end{document} for every subcubic graph G.
引用
收藏
页码:778 / 793
页数:15
相关论文
共 41 条
[1]  
Alon N(1999)Combinatorial Nullstellensatz Comb Probab Comput 8 7-29
[2]  
Bartnicki T(2009)Weight choosability of graphs J Graph Theory 60 242-256
[3]  
Grytczuk J(2013)Strong chromatic index of 2-degenerate graphs J Graph Theory 73 119-126
[4]  
Niwczyk S(2014)Neighbor sum distinguishing total coloring via the combinatorial Nullstellensatz Sin China Ser Math 57 1875-1882
[5]  
Chang G(2014)Neighbor sum distinguishing total coloring of graphs with bounded maximum average degree Acta Math Sin 30 703-709
[6]  
Narayanan N(1995)The list chromatic index of a bipartite multigraph J Comb Theory Ser B 63 153-158
[7]  
Ding L(2017)Neighbor sum distinguishing index of 2-degenerate graphs J Comb Optim 34 798-809
[8]  
Wang G(2017)A note on Discrete Math Algorithm Appl 9 1750011-1366
[9]  
Yang G(2017)-choosability of plane graphs under distance restrictions Discrete Math Algorithm Appl 9 1750031-688
[10]  
Dong A(2017)Rado Discrete Math Algorithm Appl 9 1750047-782