Asymptotically optimal neighbor sum distinguishing total colorings of graphs

详细信息    查看全文

• 作者：Sarah Loeb^a ; ^{sloeb2@illinois.edu} ; Jakub Przybyło^b ; ^{jakubprz@agh.edu.pl} ; Yunfang Tang^c ; ^{tangyunfang8530@gmail.com}
• 关键词：Neighbor sum distinguishing index ; Neighbor sum distinguishing total coloring
• 刊名：Discrete Mathematics
• 出版年：2017
• 出版时间：6 February 2017
• 年：2017
• 卷：340
• 期：2
• 页码：58-62
• 全文大小：394 K
• 卷排序：340

文摘

Given a proper total kk-coloring c:V(G)∪E(G)→{1,2,…,k}c:V(G)∪E(G)→{1,2,…,k} of a graph GG, we define the value   of a vertex vv to be c(v)+∑uv∈E(G)c(uv)c(v)+∑uv∈E(G)c(uv). The smallest integer kk such that GG has a proper total kk-coloring whose values form a proper coloring is the neighbor sum distinguishing total chromatic number   of GG, χΣ′′(G). Pilśniak and Woźniak (2013) conjectured that χΣ′′(G)≤Δ(G)+3 for any simple graph with maximum degree Δ(G)Δ(G). In this paper, we prove this bound to be asymptotically correct by showing that χΣ′′(G)≤Δ(G)(1+o(1)). The main idea of our argument relies on Przybyło’s proof (2014) regarding neighbor sum distinguishing edge-colorings.