/^creative ^commor
ARS MATHEMATICA CONTEMPORANEA
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 11 (2016) 79-89
Distinguishing graphs by total colourings*
Rafal Kalinowski, Monika Pilsniak, Mariusz WoZniak t
Department of Discrete Mathematics, AGH University, Krakow, Poland
Received 26 October 2014, accepted 22 July 2015, published online 24 September 2015
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) for every connected graph G.
We also introduce the total distinguishing chromatic number x'D (G) similarly defined for proper total colourings of a graph G. We prove that xD (G) < x""(G) + 1 for every connected graph G with the total chromatic number x""(G). Moreover, if x""(G) > A(G) + 2, then xD (G) = x "(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: Total colourings of graphs, symmetry breaking in graphs, total distinguishing number, total distinguishing chromatic number
Math. Subj. Class.: 05C15, 05E18
1 Introduction and definitions
In 1996, Albertson and Collins [1] introduced the distinguishing number D(G) of a graph G as the least number d such that G admits a vertex colouring with d colours that is only preserved by the trivial automorphism of G. Ten years later Collins and Trenk [3] defined the distinguishing chromatic number xd (G) of a graph G for proper vertex colourings, so xD (G) is the least number d such that G has a proper colouring with d colours that is
*The research was partially supported by the Polish Ministry of Science and Higher Education. t Supported by the NCN grant DEC-2013/09/B/ST1/01772; research was done during his visit at the Institut Mittag-Leffler (Djursholm, Sweden)
E-mail addresses: kalinows@agh.edu.pl (Rafal Kalinowski), pilsniak@agh.edu.pl (Monika Pilsniak), mwozniak@agh.edu.pl (Mariusz Wozniak)
©® This work is licensed under http://creativecommons.org/licenses/by/3.0/
80
Ars Math. Contemp. 11 (2016) 35-47
only preserved by the trivial automorphism. These concepts have already spawned tens of papers. For endomorphisms instead of automorphisms this approach was investigated in
[4].
Obviously, D(G) = 1 for all asymmetric graphs. On the other hand, for a complete graph Kn and a complete bipartite graph Kp,p we have D(Kn) = n, and D(Kp,p) = p +1. The distinguishing number of cycles C3,C4, C5 equals three, while cycles Cn of length n > 6 have distinguishing number two.
This compares with a more general result of Collins and Trenk [3], and of KlavZar, Wong and Zhu [7].
Theorem 1.1. [3],[7] If G is a connected graph with maximum degree A, then D(G) < A + 1. Furthermore, equality holds if and only if G is a Kn, Kp,p or C5.
In the same paper [3], Collins and Trenk obtained a general bound for the distinguishing chromatic number.
Theorem 1.2. [3] If G is a connected graph with maximum degree A, then xd (G) < 2A. Furthermore, equality is achieved if and only if G is a Kp,p or C6.
Edge colourings breaking automorphisms were investigated by the first two authors in
[5].	If a graph G does not contain K2 as a connected component, then the distinguishing index D'(G) of a graph G as the least number d such that G admits an edge colouring with d colours that is only preserved by the trivial automorphism. And the distinguishing chromatic index xDd (G) of a graph G is the least number d such that G has a proper edge colouring with d colours that is not preserved by any nontrivial automorphism of G. A general upper bound for the distinguishing index was proved therin.
Theorem 1.3. [5] If G is a connected graph of order n > 3 with maximum degree A, then D'(G) < A unless G is C3, C4 or C5.
It was also proved in [5] that D'(G) < D(G) + 1 for any connected graph of order n > 3, and this bound is sharp for each n. Actually, quite frequently D'(G) < D(G). For a complete graph D'(Kn) = 2 for any n > 6, and also for a complete bipartite graph D'(Kp,p) = 2 forp > 4, whereas D(Kn) and D(Kpp) are equal to A + 1.
The following theorem gives a sharp upper bound for the distinguishing chromatic index of connected graphs.
Theorem 1.4. [5] If G is a connected graph of order n > 3, then
x'd(G) < A(G) + 1
except for four graphs of small order C4, K4, C6, K3,3.
This theorem immediately implies the following interesting fact.
Corollary 1.5. [5] Every connected Class 2 graph G admits an edge colouring with x'(G) colours that is not preserved by any nontrivial automorphism of G.
It has to be noted that Theorem 1.4 was a consequence of Theorem 1.6, the main result of [6]. To formulate it we need some definitions.
R. Kalinowski, M.Pilsniak, and M. Wozniak: Distinguishing graphs by total colourings 81
Let f : E ^ K be a proper edge colouring of a graph G = (V, E). For a given vertex x e V, each walk emanating from x defines a sequence of colors (oft. We then say that the sequence (oj) is realizable at a vertex x. The set of all sequences realizable at x is denoted by W(x). We say that two vertices x and y of a graph G are similar if W(x) = W(y), and the coloring f personalizes the vertices of G if no two vertices are similar. The minimum number of colours we need to obtain this property is denoted by ^(G) and called the vertex distinguishing index by colour walks of a graph G.
Theorem 1.6. Let G be a connected graph of order n > 3. Then
M(G) < A(G) + 1 except for four graphs of small orders: C4, K4, C6 and K3,3.
The aim of this paper is to present analogous results for total colourings. We give general bounds, and an interesting relationship between the total distinguishing chromatic number and the total chromatic number.
Definition 1.7. The total distinguishing number D"(G) of a graph G is the least number d such that G has a total colouring with d colours that is preserved only by the identity automorphism of G.
Observe that D"(G) < min{D(G), D'(G)}. Clearly the equality holds for asymmetric graphs. And also for graphs with min{D(G), D'(G)} = 2. The following observation can easily be verified.
Proposition 1.8. D"(Pn) = D"(Cn) = D"(K„) = 2 for n > 3. D"(KP}P) = 2 for p > 1.
However, quite frequently D"(G) < min{D(G), D'(G)}. For instance, for a star Ki n of size n > 3, we shall show in the next section that D"(Ki n) = |~Vn~|, while D(Ki,n) = D'(Ki,n)= n.
We shall also investigate this concept for proper total colourings. A proper total colouring f of a graph G is an assignment of colours to the vertices and edges of G such that no two adjacent edges, no two adjacent vertices and no incident edges and vertices are assigned the same colour. The least number of colours among all such colourings is called the total chromatic number denoted by x"(G).
Definition 1.9. The total distinguishing chromatic number xD (G) of a graph G is the least number d such that G has a proper total colouring with d colours that is preserved only by the identity automorphism of G.
The total chromatic number of some simple classes of graphs was investigated first by Rosenfeld in [11]. He showed that A(G) + 2 colours are enough for cliques, for complete bipartite and tripartite graphs, for balanced complete k-partite graphs and for graphs with maximum degree at most three. Next Kostochka proved the same bound for graphs with maximum degree at most four and five (see [8] and [9]). In the general case the following famous Behzad-Vizing conjecture is still open.
Conjecture 1.10. [2] For every graph G, the total chromatic number satisfies the inequality
x"(G) < A(G) + 2.
82
Ars Math. Contemp. 11 (2016) 35-47
So far, the best result in this direction was proved by Molloy and Reed in 1998.
Theorem 1.11. [10] For every graph G = (V, E), the total chromatic number satisfies the inequality
x"(G) < A(G) + 1026.
In the next section we investigate total colourings, not necessarily proper. We prove a sharp upper bound D"(G) < A(G)] for all connected graphs.
In Section 3 we investigate total proper colourings. We show how one can personalize vertices of a graph by colour walks in total colourings. This approach is analogous to that of [6] for edge colourings.
In the last section we show that x" (G)+1 colours suffice to find a total proper colouring preserved only by the trivial automorphism. We shall infer this from the results of Section 3. However, it can also be easily shown using another argument. Namely, given a proper edge colouring of a graph G, the subgroup of Aut(G) preserving the colouring acts freely on vertices, i.e., the only element fixing a vertex is the identity. This follows since all paths beginning at a given vertex v are uniquely determined by the sequence of edge colours (which in effect give directions of where to go next at each vertex in the path). Thus any color preserving automorphism fixing v must fix all vertices. This immediately implies that xDD (G) < x"(G) + 1 (just colour one vertex by an additional extra colour in a total colouring of G).
A much more intricate result of Section 4 states that xDD (G) = x"(G) whenever x"(G) > A(G) + 2 (recall that if the Behzad-Vizing conjecture is true, then every graph has a total colouring with A(G) + 1 or A(G) + 2 colours). This will be proved using the main result of Section 3 concerning personalizing vertices by colour walks in proper total colorings.
2 Total distinguishing number
Every finite tree T has either a central vertex or a central edge which is fixed by every automorphism of T. For k > 0, let Sk (x) denote a sphere of radius k with a center x, i.e., the set of all vertices at distance k from x.
Theorem 2.1. If T is a tree of order n > 3, then D"(T) < \^A(T)].
Proof. If T has a central vertex v0, then the colour of v0 can be arbitrary. Having A(T)] colours, we have at least A(T) different pairs (c1, c2) of colours, as the colouring need not be proper. Every edge incident to v0 and its end vertex in the first sphere Si(v0) obtain a distinct pair of colours (c1; c2). Hence, all vertices adjacent to v0 are fixed by every automorphism of T preserving this colouring. Next, we colour edges going to subsequent spheres of T by pairs of colours in the same way as for the first sphere. By induction on the distance from v0, all vertices of T are fixed.
If T has a central edge e0, let T1, T2 be subtrees obtained by deleting the edge e0. If we put distinct colours on the end vertices of e0, then these verices are fixed by every automorphism. Next, for i = 1,2, we colour the tree T using the same method as in the previous case.	□
To see that the bound in Theorem 2.1 is sharp, observe that for any star K1n we have D"(K1jn) = \y/A(K1jn)] = \Vn~|. Indeed, if we used less than \^n\ colours then we
R. Kalinowski, M.Pilsniak, and M. Wozniak: Distinguishing graphs by total colourings 83
have less than n pairs of colours, so there would exist at least two edges coloured identically (together with their end vertices), thus a transposition of them would be a nontrivial automorphism preserving such a colouring.
Theorem 2.2. If G is a connected graph of order n > 3, then D" (G)
Proof. Denote A = A(G). Clearly, A > 2 and we have at least two colours. If G is a tree then the claim is true by Theorem 2.1. Suppose that G contains a cycle. If G is just a cycle or a complete graph, then the claim follows from Proposition 1.8.
Otherwise, we can always choose a vertex v0 lying on a cycle such that the sphere S2 (v0) is nonempty. We colour v0 with 2 and consider a BFS tree T of G rooted at v0. We will first colour the tree T. For a given vertex v, denote
Nt(v) = {(vu,u) : vu € E(G)}.
Let Si(vo) = {vi, v2,..., vp}. Without loss of generality we can assume that vi has a neighbour in S2(v0). We colour both pairs (v0v1; v1) and (v0v2, v2) with a pair (1,1). Then we colour each pair of Nt (v0) \ {(v0 v1, v1), (v0v1, v2)} with a distinct pair of colours different from (1, 1). Thus (1, 1) appears twice as a pair of colours in Nt (v0). We will then colour the graph G in such a way that v0 will be the only vertex of G coloured with 2 such that the pair (1,1) appears twice in the neighbourhood Nt(v0). Hence v0 will be fixed by every automorphism preserving the colouring. Therefore all vertices in S1(v0) will also be fixed, except, possibly v1 and v2. To distinguish v1 and v2, we colour the sets {(v1u,u) € Nt(v1) : u € £2^0)} and {(v2u,u) € Nt(v2) : v2u € E(T),u € S2(v0)} with two distinct sets of pairs of colours (this is possible since each of these sets contains at most A - 1 elements, and we have A distinct pairs of colours). Therefore, every vertex adjacent to v0, v1 or v2 will be fixed by every automorphism preserving our colouring. For each i = 3,... ,p, we then colour all elements of {(vju, u) : v4u € E(T),u € S2(v0)} with distinct pairs of colours different from the pair (1,1). This is again possible. Thus, all other vertices in S2(v0) will be also fixed.
Then we proceed recursively with respect to the radius k of subsequent spheres Sk (v0) according to the ordering of vertices of the BFS tree T. Suppose all vertices of Sj(v0) = {u1,..., ui.}, i = 0,..., k, are fixed by every automorphism preserving colours. For each
84
Ars Math. Contemp. 11 (2016) 35-47
subsequent vertex uj , j = 1,..., lk, we colour every pair (uju, u), where u is a descendent of uj in T, with a distinct pair of colours except for (1,1). This is again possible since the number of pairs to be coloured is not greater than the number of admissible pairs of colours. Thus all neighbours of uj in Sfc+1(v0) will be also fixed.
Finally, we colour all remaining edges in E(G) \ E(T) with 2. It is easily seen that if v is a vertex coloured with 2 such that the pair of colours (1,1) appears twice in Nt(v), then v = v0. Hence, all vertices of G are fixed by any automorphism preserving this colouring.	□
Theorem 2.2 does not hold for disconnected graphs. For instance, consider a graph G of order n being the sum of r pairwise disjoint copies of K2, i.e., G = rK2 with n = 2r. It is easy to see that D"(rK2) = min{k : k2(k - 1) > r}. Hence, D"(rK2) > {ff while A(rK2) = 1.
3 Personalizing vertices by total colour walks 3.1 Total colour walks
In this section, we consider only proper colourings. Let f be a proper total colouring of a graph G = (V, E). The total palette of a vertex v is the set
S(v) = {f (u)} U {(f (vu),f (u)) : uv e E}.
For a given vertex x e V, each walk emanating from x, say xe1x1e2x2 ...epxp,
where ej — xj_ixi is an edge of G, i = 1,2,... ,p, defines a sequence of colours
(f (x), f (ei), f (xi), f (e2), f (x2),..., f (ep), f (xp)). We then say that this sequence of colours is realizable at the vertex x. The set of all sequences realizable at x is denoted by
W (x).
We say that two vertices x and y of a graph G are similar with respect to f if W(x) = W(y), and the colouring f personalizes the vertices of G if no two vertices are similar. The minimum number of colours we need to obtain this property is denoted by t(G), and called the vertex distinguishing index by total colour walks of a graph G.
Denote by Wk (x) all sequences of W(x) of length 2k + 1, i.e., generated by all walks of length k. We see that the total palette of a vertex v can be identified with W1 (v).
For a given («j) e W(x), denote by m(x, (a)) the last vertex on a walk emanating from x and defining the sequence (oj). The following observation will be used several times in the proof of our main result.
Proposition 3.1. Two vertices x and y of G are similar if and only if for each («j) e W (x), we have («j) e W (y) and the vertices m(x, («,)), m(y, (oj)) have the same total palettes.
An analogous notion for edge colouring has been introduced in [6]. The corresponding parameter was denoted by p(G). The main result of [6] was Theorem 1.6. In particular it follows that m(G) = x'(G) if X'(G) = A(G) + 1.
The aim of this section is to prove an analogous result for total colourings. More precisely we shall prove the following theorem.
Theorem 3.2. Let G be a connected graph. Then
t(G) < x"(G) + 1.
R. Kalinowski, M.Pilsniak, and M. Wozniak: Distinguishing graphs by total colourings 85
Moreover, if x''(G) > A(G) + 2 then t(G) = x''(G).
The proof of this theorem is divided into two parts. First, in the subsection below, we prove that t(G) < x''(G) + 1. In the next subsection, we prove the second part of the theorem for graphs with x"(G) > A(G) + 2.
The above inequalities concerning t(G) need not be true for disconnected graphs. For instance, consider again a graph G = rK2 with n = 2k. It is easy to see that t(rK2) = min{k : 3(3) > r}. Hence, t(rK2) > ffi while A(rK2) = 1 and x''(rK2) = 3.
3.2	Graphs with x"(G) = A(G) + 1
In this subsection we prove Theorem 3.2 in case x"(G) = A(G)+1. Let f : VUE ^ K be a colouring of G with x''(G) colours. Let x be a vertex of G. We define a new colouring f' of G by replacing f (x) with a new colour 0 G K. We show that this colouring personalizes the vertices of G.
For, suppose that there are two similar vertices u and v. Denote by Q a shortest path from u to the vertex x. Consider now the walk Q' starting at v and inducing the same colour sequence as Q. Evidently, the walk Q' should also finish in x. The crucial observation is that since the last edges of Q and Q' are of the same colour, they cannot arrive to the same vertex and, since x is the only vertex of colour 0, we get a contradiction.
3.3	Graphs with x''(G) > A(G) + 2
Now, we shall prove Theorem 3.2 in case x''(G) > A(G) + 2. Let f : V U E ^ K be a proper total colouring of a graph G = (V, E) with x' (G) colours, and let x' (G) > A(G) + 2. Assume for the rest of this subsection that there is no proper total colouring of G using x' (G) colours which personalizes the vertices of G. For convenience, we will formulate stages of the proof as observations.
Denote by N(x) and E(x) the set of vertices adjacent to x and the set of edges incident to x, respectively, and let NV(x) = f (N(x)) and E(x) = f (E(x)).
Observation 3.3. For each vertex x g V, the set {f (x)}UNV(x)UE(x) contains all colours of K.
Proof. Suppose that there is a vertex x andacolour a such that a g K \ ({f (x)}U NV(x) U E(x)). We shall show that then f could be modified in such a way that the obtained colouring would personalize the vertices of G.
Denote by Y the set of all vertices y with Wi(y) = Wi(x). If Y contains only the vertex x, we are done. For, we can repeat the reasoning from the previous subsection by considering the walks ending with x.
If Y contains more vertices, we replace f (y) by a in each vertex y g Y, y = x. In this way, x becomes the only vertex of G with the palette W1(x). Again, we can repeat the reasoning from the previous subsection by considering the walks ending with x.	□
Observation 3.4. For each edge xy g E the set {f (x)} U {f (y)} U E(x) U E(y) contains all colours of K.
Proof. Let us suppose that there is an edge xy and a colour a such that a g K \ ({f (x)} U {f (y)}U E(x) U E(y)).
Consider now the set F of all edges x'y' such that f (x'y') = f (xy) and W1(x) = W1(x') and W1(y) = W1(y'). Assume first that there exists only one such edge, namely
86
Ars Math. Contemp. 11 (2016) 35-47
xy. Then, our colouring personalizes the vertices of G. For, suppose that there are two similar vertices u and v. Denote by Q a shortest path joining u with the edge xy. Consider now the walk Q' starting at v and inducing the same colour sequence as Q. Evidently, the walk Q' should also attain the edge xy.
Since the last edges of Q and Q' are of the same colour, they cannot arrive at the same vertex. So, one of the walks Q and Q' finishes at x and the other one at y. Since the palettes at x and y are distinct, we are done by Proposition 3.1.
If F contains more edges, we replace f (x'y') by a for all edges of F exept for the edge xy. In this way, xy becomes the only edge of G coloured with f (xy) and having the palettes Wi(x) and Wi(y) on its ends. Therefore, we can repeat the reasoning from above.	□
A vertex x is a-free if a G {f (x)} U E(x).
Observation 3.5. For each vertex x, there is a colour, say a, such that x is a-free.
Proof. It suffices to observe that the set {f (x)} U E(x) contains exactly d(x) +1 elements while the number of colours is greater than A(G) + 1.	□
We say that a set of edges incident to a vertex x of G forms a cyclic structure of size p > 2 (with respect to the colouring f) if these edges can be ordered as xy^ i = 1,..., p, such that the vertex yj is f (xyj+1)-free, for i = 1,... ,p, where the indexes are taken modulo p. Then the vertex x is called central while the vertices yj are leaves of the cyclic structure.
The significance of a cyclic structure is shown by the next two observations. The proof of the first one follows immediately from the definition of the cyclic structure.
Observation 3.6. If the edges xyj, i = 1,... ,p, form a cyclic structure, then we can rotate the colours of edges, i.e., replace the colour f (xyj) on the edge xyj by the colour f (xyi+1), and the obtained colouring of G remains proper.
Observation 3.7. For each vertex x, the set E(x) contains a cyclic structure.
Proof. Let x be a vertex of G and denote f (x) by 0. Since the set {x} U N(x) has at most A(G) + 1 < x''(G) elements, there is a colour, say a, which does not belong to the set {f (x)} U NV(x). Then, by Observation 3.3, a G E(x). Denote by yo the second end of the edge incident to x and coloured by a. By Observation 3.5, there is a colour, say y1, such that the vertex y0 is Y1-free.
If y1 =0 we can put the colour 0 on the edge xy0 and the colour a on the vertex x. In consequence, we are able to reduce the number of vertices having the same palette as x by one, and then eventually get only one such vertex. This would provide a proper total colouring personalizing the vertices of G.
So, we may assume that y1 = 0. Then, by Observation 3.4, y1 g E(x). Let xy1 be the edge coloured with y1. Again, by Observation 3.5, there is a colour, say Y2, such that the vertex y1 is Y2-free.
If Y2 = 0 we can put the colour 0 on the edge xy1 , the colour Y1 on the edge xy0 and the colour a on the vertex x (see Figure 2). In consequence, we are able to reduce the number of vertices having the same palette as x to obtain eventally only one such vertex. This would provide a colouring personalizing vertices of G.
If y2 = a, the edges xy1, xy2 form a cyclic structure of size two.
R. Kalinowski, M.Pilsniak, and M. Wozniak: Distinguishing graphs by total colourings 87
Figure 2: Before and after the change described in the proof of Observation 3.7
If 72 = 0 and y2 = a, we continue the procedure of choosing at each step, as the missing colour, the first possible colour from the sequence 0, a, y1 , y2 ,.... If such a choice is possible, we can either exchange the colours and get a situation where x has a unique total palette, or we obtain a cyclic structure.
If the procedure finishes without finding 0 as a missing colour and without finding a cyclic structure, then the last vertex yd-1, where d = d(x), is Yd-free for some Yd £ {0, a, Y1,..., Yd-1}. It means, in particular, that also the vertex x is Yd-free, a contradiction with Observation 3.4.	□
Let the set Cyc1 of edges , i = 1,... ,p, incident to a vertex x of G, be a cyclic structure of size p (with respect to the colouring f). If all the vertices yj, i = 1,... ,p, have the same colour, say then the palette at x remains unchanged after the rotation described in Observation 3.6. Therefore, we need a somewhat more complicated structure.
Suppose that a set Cyc2 is another cyclic structure of size q with a central vertex x distinct from x. If Cyc1 and Cyc2 have a leave in common then we say that the sets Cyc1 and Cyc2 form a double cyclic structure.
Observation 3.8. If G has at least one double cyclic structure with respect to the colouring f then this colouring can be modified such that a new colouring personalizes the vertices of G.
Proof. Suppose that two sets of edges Cyc1 = {xyj : i = 1,... ,p} and Cyc2 = {xzj : j = 1,..., q} form a double cyclic structure. Without loss of generality we may assume that y1 = z1. Denote f (y1) = f (z1) = ft and f (z1x) = J1.
Let Y be the set of all vertices y with W2 (x) = W2 (y). If Y contains only the vertex x, we are done by repeating the reasoning from the previous subsection with the walks ending at x.
If Y contains more than one vertex, then each vertex y belonging to Y and different from x, is a central vertex of a cyclic structure of size p which is a part of a double cyclic structure with the second part being of size q.
Now, for each vertex y £ Y \{x}, we rotate the colours of edges of the cyclic structure of size q forming the second part of a double cyclic structure. In this new colouring f' the set W2(y) does not contain the sequence (f (x), y1; f (x)) which was and still is present in W2' (x). In consequence, f' is a colouring such that W2' (x) = W2' (y) for every vertex y distinct from x. It follows that f' personalizes the vertices of G.	□
88
Ars Math. Contemp. 11 (2016) 35-47
The next observation finishes the proof of Theorem 3.2.
Observation 3.9. Each graph G has at least one double cyclic structure.
Proof. For each vertex x we choose one cyclic structure Cyc(x) having x as a central vertex. The existence of such a structure is assured by Observation 3.7.
Consider now an auxiliary digraph r defined in the following way. The vertex set V(r) coincides with the vertex set V (G) and the arcs of r are the edges of G belonging to all sets Cyc(x) oriented from a central vertex of a structure towards the leaves of it.
By definition of a cyclic structure we have d+(x) > 2 for each x. This implies, in particular, that there exists at least one vertex, say u, with d-(u) > 2. Denote by z and z two of its in-neighbours in r. Then, the set Cyc(z) U Cyc(z) forms a double cyclic structure.	□
4 Total distinguishing chromatic number
The following lemma exhibits a relationship between t(G) and xD (G). Lemma 4.1. Every connected graph G of order n > 3 fulfils the inequality
Xd (G) < t(G).
Proof. Let f be a proper total colouring personalizing the vertices of G by colour walks, i.e., W(x) = W(y) if x = y. Suppose ^ is a nontrivial automorphism of G preserving f. Then there exists a vertex x such that x = y(x). An automorphism ^ preserves the colouring, so every sequence (oj) G W(x) belongs also to W(y(x)). And every sequence ) starting at y(x), starts also at ^>-1(^>(x)) = x. Hence, x and ^(x) are not distinguished by
colour walks in this colouring.	□
□
As a consequence of Lemma 4.1 and Theorem 3.2 we obtain a sharp upper bound for the distinguishing chromatic number of connected graphs.
Theorem 4.2. Every connected graph G fulfils the inequality
Xd (G) < x"(g) + 1.
Moreover, xD(G) = x"(G) if x"(G) > A(G) + 2.
A total proper colouring of G with x"(G) colours is called minimal. This theorem immediately implies the following interesting result.
Corollary 4.3. Every connected graph G with x"(G) > A(G) + 2 admits a minimal total colouring that is not preserved by any nontrivial automorphism.
For graphs with x"(G) = A(G) + 1, we sometimes need one colour more for xD (G) than x"(G).
For instance, cycles of order 6k, for all k > 1, have a unique (up to a permutation of colours) colouring with three colours and this colouring is preserved by some rotations. Thus xD(Cefc) = x"(Cefc) + 1, by Theorem 4.2.
R. Kalinowski, M.Pilsniak, and M. Wozniak: Distinguishing graphs by total colourings 89
Figure 3: A minimal proper total colouring of C6 with three colours. References
[1]	M. O. Albertson and K. L. Collins, Symmetry breaking in graphs, Electron. J. Combin. 3 (1996), R18.
[2]	M. Behzad, Graphs and their chromatic numbers, Ph.D. Thesis, Michigan State University, 1965.
[3]	K. L. Collins and A. N. Trenk, The distinguishing chromatic number, Electron. J. Combin. 13 (2006), R16.
[4]	W. Imrich, R. Kalinowski, F. Lehner and M. Pilsniak, Endomorphism Breaking in Graphs, Electron. J. Combin. 21 (2014), P1.16.
[5]	R. Kalinowski and M. Pilsniak, Distinguishing graphs by edge-colourings, European J. Combin. 45 (2015), 124-131.
[6]	R. Kalinowski, M. Pilsniak, J.Przybylo, M. WoZniak, How to personalize the vertices of a graph?, European J. Combin. 40 (2014), 116-123.
[7]	S. KlavZar, T.-L. Wong and X. Zhu, Distinguishing labelings of group action on vector spaces and graphs, J. Algebra 303 (2006), 626-641.
[8]	A. V. Kostochka, The total coloring of a multigraph with maximal degree 4, Discrete Mathematics 17 (1977), 161-163.
[9]	A. V. Kostochka, Upper bounds of chromatic functions of graph (in Russian), Ph.D. Thesis, Novosibirsk, 1978.
[10]	M. Molloy, B. Reed, A bound on the total chromatic number, Combinatorica 18 (1998), 241280.
[11]	M. Rosenfeld, On the total coloring of certain graphs, Israel Journal of Mathematics 9 (1970), 396-402.