Conjecture (Csóka-Lippner-Pikhurko). If $G$ is a graph with each vertex of degree $\le d$ with at most $d-1$ pendant edges properly coloured, then this pre-colouring can be extended to all edges of $G$, using $d+1$ colours in total.

If proved, this will directly give new bounds on questions of Albert (2010) & Marks (2016) on measurable Vizing's theorem.

(This problem was written 23.08.2018 by Oleg Pikhurko on page 51 of Volume 2 of the Lviv Scottish Book).

  • 1
    $\begingroup$ I am confused. Do we colour edges or vertices? What are pending edges? $\endgroup$ – Fedor Petrov Oct 22 '18 at 23:05
  • $\begingroup$ @FedorPetrov If I understood the problem correctly, we colour edges and pending edges are edges that contain a vertex of degree 1. But I will contact Oleg Pikhurko and will ask him to comment on this. $\endgroup$ – Lviv Scottish Book Oct 23 '18 at 9:16
  • $\begingroup$ Still unclear. What are restrictions on the graph and what is already coloured? $\endgroup$ – Fedor Petrov Oct 23 '18 at 9:54
  • 1
    $\begingroup$ @FedorPetrov I added the link (just after "Conjecture") to the original paper of Csoka-Lippner-Pikhurko (doi.org/10.1017/fms.2016.22). This conjecture is Conjecture 1.7. Definition 1.6 explains the terminology. $\endgroup$ – Lviv Scottish Book Oct 23 '18 at 10:01

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.