The pre-colored leaf extension conjecture

Let f(k)f(k) be the smallest integer ff such that for every d[k]d\in[k] the following holds. Let GG be an arbitrary finite graph such that every degree is at most dd, except at most one vertex of degree d+1d+1. Suppose that at most d1d-1 leaves, that is, edges with one of their endpoints having degree 11, are pre-colored. Then this pre-coloring can be extended to an edge-coloring of the whole graph GG that uses at most d+fd+f different colors. Pre-colored leaf extension conjecture. f(k)=1f(k)=1 for all k1k\geqslant 1. This conjecture would strengthen Vizing's theorem by asserting that the specified pre-coloring can always be extended using only d+1d+1 colors, even when one vertex has degree d+1d+1.

Sources & referencesView supporting material

Primary source

Endre Csóka, Gabor Lippner and Oleg Pikhurko, “Kőnig's Line Coloring and Vizing's Theorems for Graphings”, arXiv:1408.1973 (2016).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.