Speaker
Rafal Kalinowski
(AGH University)
Description
The *distinguishing index* $D'(G)$ of a graph $G$ is the least number of colours of an edge colouring that is not preserved by any non-trivial automorphism.
The following result was proved by Pil\'sniak in [1].
**Theorem.** If $G$ is a connected graph, then
$(1)$ $D'(G)=\Delta(G)+1$ iff $G$ is a cycle of length less than $6$,
$(2)$ $D'(G)=\Delta(G)$ iff $G$ is a symmetric or a bisymmetric tree, a cycle of length at least $6$, or $K_4$ or $K_{3,3}$,
$(3)$ $D'(G)\leq\Delta(G)-1$ otherwise.
In the same paper, Pil\'sniak formulated the following conjecture.
**Conjecture.** If a graph $G$ is $2$-connected, then $$D'(G)\leq \left\lceil\sqrt{\Delta(G)}\right\rceil+1.$$
In this talk, we prove this conjecture in a bit stronger form, and show some of its consequences.
Reference:
[1] M. Pil\'sniak, Improving upper bounds for the distinguishing index, Ars Math. Contemp. 13 (2017) 259--274.
Primary author
Rafal Kalinowski
(AGH University)
Co-authors
Mariusz Wozniak
(AGH University)
Monika Pilsniak
(AGH University, Krakow, Poland)
Wilfried Imrich
(Montanuniversitaet Leoben)
