Equitable neighbour-sum-distinguishing edge and total colourings

• Published in: Discrete Applied Mathematics 2017-05, Vol.222, p.40-53
• Main Authors: Baudon, Olivier, Pilśniak, Monika, Przybyło, Jakub, Senhaji, Mohammed, Sopena, Éric, Woźniak, Mariusz
• Format: Article
• Language: English
• Subjects: Combinatorics; Computer Science; Discrete Mathematics; Equitable colouring; Geometry; Graph coloring; Graph theory; Graphs; Mathematics; Neighbour-sum-distinguishing edge colouring; Neighbour-sum-distinguishing total colouring; Studies
• ISSN: 0166-218X; 1872-6771
• DOI: 10.1016/j.dam.2017.01.031

With any (not necessarily proper) edge k-colouring γ:E(G)⟶{1,…,k} of a graph G, one can associate a vertex colouring σγ given by σγ(v)=∑e∋vγ(e). A neighbour-sum-distinguishing edge k-colouring is an edge colouring whose associated vertex colouring is proper. The neighbour-sum-distinguishing index of a graph G is then the smallest k for which G admits a neighbour-sum-distinguishing edge k-colouring. These notions naturally extend to total colourings of graphs that assign colours to both vertices and edges. We study in this paper equitable neighbour-sum-distinguishing edge colourings and total colourings, that is colourings γ for which the number of elements in any two colour classes of γ differ by at most one. We determine the equitable neighbour-sum-distinguishing index of complete graphs, complete bipartite graphs and forests, and the equitable neighbour-sum-distinguishing total chromatic number of complete graphs and bipartite graphs.