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.

  • $\begingroup$ Usually, MO is not meant to simply state known open problems, see for example "meta.mathoverflow.net/questions/360/…" $\endgroup$ – verret Oct 23 '18 at 18:16
  • $\begingroup$ @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. $\endgroup$ – Lviv Scottish Book Oct 23 '18 at 18:32
  • 1
    $\begingroup$ @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 :) $\endgroup$ – Lviv Scottish Book Oct 26 '18 at 20:22
  • $\begingroup$ @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. $\endgroup$ – Lviv Scottish Book Oct 27 '18 at 7:38
  • 1
    $\begingroup$ @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)? $\endgroup$ – Lviv Scottish Book Oct 27 '18 at 18:21

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.