首页 | 本学科首页   官方微博 | 高级检索  
     


Neighbor sum distinguishing total coloring of graphs with bounded treewidth
Authors:Miaomiao Han  You Lu  Rong Luo  Zhengke Miao
Affiliation:1.College of Mathematical Science,Tianjin Normal University,Tianjin,People’s Republic of China;2.Department of Applied Mathematics, School of Science,Northwestern Polytechnical University,Xi’an,People’s Republic of China;3.Department of Mathematics,West Virginia University,Morgantown,USA;4.School of Mathematics and Statistics,Jiangsu Normal University,Xuzhou,People’s Republic of China
Abstract:A proper total k-coloring (phi ) of a graph G is a mapping from (V(G)cup E(G)) to ({1,2,dots , k}) such that no adjacent or incident elements in (V(G)cup E(G)) receive the same color. Let (m_{phi }(v)) denote the sum of the colors on the edges incident with the vertex v and the color on v. A proper total k-coloring of G is called neighbor sum distinguishing if (m_{phi }(u)not =m_{phi }(v)) for each edge (uvin E(G).) Let (chi _{Sigma }^t(G)) be the neighbor sum distinguishing total chromatic number of a graph G. Pil?niak and Wo?niak conjectured that for any graph G, (chi _{Sigma }^t(G)le Delta (G)+3). In this paper, we show that if G is a graph with treewidth (ell ge 3) and (Delta (G)ge 2ell +3), then (chi _{Sigma }^t(G)le Delta (G)+ell -1). This upper bound confirms the conjecture for graphs with treewidth 3 and 4. Furthermore, when (ell =3) and (Delta ge 9), we show that (Delta (G) + 1le chi _{Sigma }^t(G)le Delta (G)+2) and characterize graphs with equalities.
Keywords:
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号