9
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ Usually, MO is not meant to simply state known open problems, see for example "meta.mathoverflow.net/questions/360/…" $\endgroup$
    – verret
    Oct 23, 2018 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$ Oct 23, 2018 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$ Oct 26, 2018 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$ Oct 27, 2018 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$ Oct 27, 2018 at 18:21

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.