Neighbor sum distinguishing total coloring of graphs with bounded treewidth

作者：Han, Miaomiao; Lu, You; Luo, Rong; Miao, Zhengke^*

来源：Journal of Combinatorial Optimization, 2018, 36(1): 23-34.

DOI：10.1007/s10878-018-0271-0

• Total coloring
• Neighbor sum distinguishing
• Treewidth

A proper total k-coloring of a graph G is a mapping from to such that no adjacent or incident elements in receive the same color. Let 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 for each edge Let be the neighbor sum distinguishing total chromatic number of a graph G. PilA > niak and WoAniak conjectured that for any graph G, . In this paper, we show that if G is a graph with treewidth and , then . This upper bound confirms the conjecture for graphs with treewidth 3 and 4. Furthermore, when and , we show that and characterize graphs with equalities.

• 出版日期2018-7
• 单位西北工业大学; 天津师范大学; 江苏师范大学