# Minimal number of colours in distinguishing colouring of biconnected graphs

A colouring of edges of a graph is distingushing if no non-identity automorphism of the graph preserves this colouring.

Problem. Is it true that each biconnected graph possesses a distinguishing colouring using $$1+\lceil\Delta^{1/\delta}\rceil$$ colours?

Here $$\Delta$$ and $$\delta$$ stand for the largest and smallest degree of a vertex of the graph. The colouring needs not be proper, i.e., adjacent edges can be coloured by the same colour.

A graph is biconnected if it remains connected after removing any vertex and its incident edges.

(The problem is posed 07.04.2018 by Imrich, Kalinowski and Pilsniak on page 21 of Volume 1 of the Lviv Scottish Book).

Prize for solution: Strudel i kawa przed seminarium w Katedrze matematyki dyskretnej AGH, na ktorym autor przedstawi rozwiazanie.

• Usually, MO is not meant to simply state known open problems, see for example "meta.mathoverflow.net/questions/360/…" – verret Oct 23 '18 at 18:16
• @verret You are right. The problems should be original posed by the authors of the posts in Lviv Scottish Book. Could you please give a link to a source where this concrete problem has been posed or discussed. Thank you. – Lviv Scottish Book Oct 23 '18 at 18:32
• @Kaban-5 Indeed, this seems to be a counteexample. Please write it as a formal answer and I will try to contact the authors of this problem. According to their promise (written in the Lviv Scottish Book), they should invite you to deliver a talk on their seminar in AGH, Krakow (it is a nice tourist city :) – Lviv Scottish Book Oct 26 '18 at 20:22
• @Kaban-5 I have contacted the authours of this problem and one of them wrote me that they had in mind edge colouring writing "kolorowanie grafu", not vertex colouring. So I made a wrong translation of this question into English. Sorry for that. For the edge colourings you example $K_{n,n}$ does not fit as this graph admits a distinguishing edge colouring with 2 colours (I do not see which exactly), but an author of the problem wrote that because $K_{n,n}$ is tracable. – Lviv Scottish Book Oct 27 '18 at 7:38
• @Kaban-5 Oh, sorry! I did not read the problem carefully enough and translated "dwospojny" (i.e., biconnected) as "bipartite". This was a reason of misunderstanding. Now it is corrected to biconnected. Maybe it is reasonable just to delete all comments related to bipartite graphs to avoid further mesunderstanding (of future readers)? – Lviv Scottish Book Oct 27 '18 at 18:21