Distinguishing graphs by total colourings

Rafał Kalinowski, Monika Pilśniak, Mariusz Woźniak


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.


Total colourings of graphs, symmetry breaking in graphs, total distinguishing number, total distinguishing chromatic number

Full Text:


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