Adjacent vertex distinguishing total coloring of graphs with maximum degree 4

详细信息    查看全文

• 作者：You Lu^a ; ^{luyou@nwpu.edu.cn} ; Jiaao Li^b ; ^{joli@mix.wvu.edu} ; Rong Luo^b ; ^{rluo@math.wvu.edu} ; Zhengke Miao^c ; ^{zkmiao@jsnu.edu.cn}
• 关键词：Adjacent vertex distinguishing total coloring ; Combinatorial Nullstellensatz ; Maximum degree
• 刊名：Discrete Mathematics
• 出版年：2017
• 出版时间：6 February 2017
• 年：2017
• 卷：340
• 期：2
• 页码：119-123
• 全文大小：408 K
• 卷排序：340

文摘

Let kk be a positive integer. An adjacent vertex distinguishing (for short, AVD) totalkk-coloring ϕϕ of a graph GG is a proper total kk-coloring of GG such that no pair of adjacent vertices have the same set of colors, where the set of colors at a vertex vv is {ϕ(v)}∪{ϕ(e):e is incident to v}{ϕ(v)}∪{ϕ(e):e is incident to v}. Zhang et al. conjectured in 2005 that every graph with maximum degree ΔΔ has an AVD total (Δ+3)(Δ+3)-coloring. Recently, Papaioannou and Raftopoulou confirmed the conjecture for 44-regular graphs. In this paper, by applying the Combinatorial Nullstellensatz, we verify the conjecture for all graphs with maximum degree 4.