2017/01/17 by Olivier Baudon, Monika Pilśniak, Baudon, Olivier +9
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems #Interconnection Networks and Systems
paper · doi:10.48550/arxiv.1701.04648
openalex publication_date 2017/01/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
With any (not necessarily proper) edge k-colouring γ:E(G)\longrightarrow\1,…,k\ of a graph G,one can associate a vertex colouring σ_γ given by σ_γ(v)=∑_e\ni 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 admitsa neighbour-sum-distinguishing edge k-colouring.These notions naturally extends to total colourings of graphs that assign colours to both vertices and edges.We study in this paper equitable neighbour-sum-distinguishing edge colourings andtotal colourings, that is colourings γ for whichthe number of elements in any two colour classes of γ differ by at most one.We determine the equitable neighbour-sum-distinguishing indexof complete graphs, complete bipartite graphs and forests,and the equitable neighbour-sum-distinguishing total chromatic numberof complete graphs and bipartite graphs.