# Extending colouring of graphs using small number of colours

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).

• I am confused. Do we colour edges or vertices? What are pending edges? – Fedor Petrov Oct 22 '18 at 23:05
• @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. – Lviv Scottish Book Oct 23 '18 at 9:16
• Still unclear. What are restrictions on the graph and what is already coloured? – Fedor Petrov Oct 23 '18 at 9:54
• @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. – Lviv Scottish Book Oct 23 '18 at 10:01