The pre-colored leaf extension conjecture
The pre-colored leaf extension conjecture
Let be the smallest integer such that for every the following holds. Let be an arbitrary finite graph such that every degree is at most , except at most one vertex of degree . Suppose that at most leaves, that is, edges with one of their endpoints having degree , are pre-colored. Then this pre-coloring can be extended to an edge-coloring of the whole graph that uses at most different colors. Pre-colored leaf extension conjecture. for all . This conjecture would strengthen Vizing's theorem by asserting that the specified pre-coloring can always be extended using only colors, even when one vertex has degree .
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.