Distinguishing graphs by total colourings
Rafał Kalinowski, Monika Pilśniak, Mariusz Woźniak · Ars Mathematica Contemporanea · 2015
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.