Article ID Journal Published Year Pages File Type
419265 Discrete Applied Mathematics 2016 11 Pages PDF
Abstract

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.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
,