DIKUL - logo
E-viri
  • Neighbour sum distinguishin...
    Przybylo, Jakub

    Discrete Applied Mathematics, 03/2016, Letnik: 202
    Journal Article

    Consider a simple graph G=(V,E) and its (proper) total colouring c with elements of the set {1,2,…,k}. We say that c is neighbour sum distinguishing if for every edge uv∈E, the sums of colours met by u and v differ, i.e.,  c(u)+∑e∋uc(e)≠c(v)+∑e∋vc(e). The least k guaranteeing the existence of such a colouring is denoted χ″∑(G). We investigate a daring conjecture presuming that χ″∑(G)≤Δ(G)+3 for every graph G, 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. for many classes of graphs with unbounded maximum degree. In particular we obtain χ″∑(G)≤Δ(G)+10 for planar graphs. In fact we show that identical bounds also hold if we use any set of k real numbers instead of {1,2,…,k} as edge colours, and moreover the same is true in list versions of the both concepts.