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

The main motivation for us stating this conjecture was that, if the conjecture is true, then Vizing's theorem holds for every graphing. Since the latter result was recently proved by Jan Grebik and me (in https://arxiv.org/abs/1905.01716) via a different route, the conjecture is not so interesting now.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.