### Distinguishing graphs by total colourings

#### Abstract

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.

#### Keywords

DOI: https://doi.org/10.26493/1855-3974.751.9a8

ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications