Equitable neighbour-sum-distinguishing edge and total colourings

With any (not necessarily proper) edge \(k\)-colouring \(\gamma:E(G)\longrightarrow\{1,\dots,k\}\) of a graph \(G\),one can associate a vertex colouring \(\sigma\_{\gamma}\) given by \(\sigma\_{\gamma}(v)=\sum\_{e\ni v}\gamma(e)\).A neighbour-sum-distinguishing edge \(k\)-colouring is an edge colour...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2017-01
Main Authors: Baudon, Olivier, Pilsniak, Monika, Przybylo, Jakub, Senhaji, Mohammed, Sopena, Eric, Wozniak, Mariusz
Format: Article
Language:English
Subjects:
Apexes
Graph coloring
Graph theory
Graphs
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:With any (not necessarily proper) edge \(k\)-colouring \(\gamma:E(G)\longrightarrow\{1,\dots,k\}\) of a graph \(G\),one can associate a vertex colouring \(\sigma\_{\gamma}\) given by \(\sigma\_{\gamma}(v)=\sum\_{e\ni v}\gamma(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 \(\gamma\) for whichthe number of elements in any two colour classes of \(\gamma\) 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.
ISSN:2331-8422