We introduce the total distinguishing number Dʺ(G) of a graph G as the least number d such that G has a total colouring (not necessarily proper) with d colours that is only preserved by the trivial automorphism. This is an analog to the notion of the distinguishing number D(G), and the distinguishing index Dʹ(G), which are defined for colourings of vertices and edges, respectively. We obtain a general sharp upper bound: Dʺ(G) ≤ ⌈√Δ (G)⌉ for every connected graph G.We also introduce the total distinguishing chromatic number χʺD(G) similarly defined for proper total colourings of a graph G. We prove that χʺD(G) ≤ χʺ(G) + 1 for every connected graph G with the total chromatic number χʺ(G). Moreover, if χʺ(G) ≥ Δ (G) + 2, then χʺD(G) = χʺ(G). We prove these results by setting sharp upper bounds for the minimal number of colours in a proper total colouring such that each vertex has a distinct set of colour walks emanating from it.
@article{751,
title = {Distinguishing graphs by total colourings},
journal = {ARS MATHEMATICA CONTEMPORANEA},
volume = {11},
year = {2015},
doi = {10.26493/1855-3974.751.9a8},
language = {EN},
url = {http://dml.mathdoc.fr/item/751}
}
Kalinowski, Rafał; Pilśniak, Monika; Woźniak, Mariusz. Distinguishing graphs by total colourings. ARS MATHEMATICA CONTEMPORANEA, Tome 11 (2015) . doi : 10.26493/1855-3974.751.9a8. http://gdmltest.u-ga.fr/item/751/