Neighbor sum distinguishing total colorings via the Combinatorial Nullstellensatz |
| |
Authors: | LaiHao Ding GuangHui Wang GuiYing Yan |
| |
Institution: | 1. Department of Mathematics, Shandong University, Jinan, 250100, China 2. Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing, 10080, China
|
| |
Abstract: | Let G = (V,E) be a graph and φ be a total coloring of G by using the color set {1, 2, ...,k}. Let f(ν) denote the sum of the color of the vertex ν and the colors of all incident edges of ν. We say that φ is neighbor sum distinguishing if for each edge uν ∈ E(G), f(u) ≠ f(ν). The smallest number k is called the neighbor sum distinguishing total chromatic number, denoted by χ nsd″(G). Pil?niak and Wo?niak conjectured that for any graph G with at least two vertices, χ nsd″(G) ? Δ(G) + 3. In this paper, by using the famous Combinatorial Nullstellensatz, we show that χ nsd″(G) ? 2Δ(G)+col(G)?1, where col(G) is the coloring number of G. Moreover, we prove this assertion in its list version. |
| |
Keywords: | neighbor sum distinguishing total coloring coloring number Combinatorial Nullstellensatz list total coloring |
本文献已被 CNKI SpringerLink 等数据库收录! |
|