کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419265 | 683763 | 2016 | 11 صفحه PDF | دانلود رایگان |

Consider a simple graph G=(V,E)G=(V,E) and its (proper) total colouring cc with elements of the set {1,2,…,k}{1,2,…,k}. We say that cc is neighbour sum distinguishing if for every edge uv∈Euv∈E, the sums of colours met by uu and vv differ, i.e., c(u)+∑e∋uc(e)≠c(v)+∑e∋vc(e)c(u)+∑e∋uc(e)≠c(v)+∑e∋vc(e). The least kk guaranteeing the existence of such a colouring is denoted χ″∑(G)χ″∑(G). We investigate a daring conjecture presuming that χ″∑(G)≤Δ(G)+3χ″∑(G)≤Δ(G)+3 for every graph GG, a seemingly demanding problem if confronted with up-to-date progress in research on the Total Colouring Conjecture itself.We note that χ″∑(G)≤Δ(G)+2col(G)−1 and apply Combinatorial Nullstellensatz to prove a stronger bound: χ″∑(G)≤Δ(G)+⌈53col(G)⌉. This imply an upper bound of the form χ″∑(G)≤Δ(G)+constχ″∑(G)≤Δ(G)+const. for many classes of graphs with unbounded maximum degree. In particular we obtain χ″∑(G)≤Δ(G)+10χ″∑(G)≤Δ(G)+10 for planar graphs.In fact we show that identical bounds also hold if we use any set of kk real numbers instead of {1,2,…,k}{1,2,…,k} as edge colours, and moreover the same is true in list versions of the both concepts.
Journal: Discrete Applied Mathematics - Volume 202, 31 March 2016, Pages 163–173