Multigraph edge-coloring with local list sizes

07/22/2023

∙

by   Abhishek Dhawan, et al.

∙

0

∙

share

Let G be a multigraph and L : E(G) → 2^ℕ be a list assignment on the edges of G. Suppose additionally, for every vertex x, the edges incident to x have at least f(x) colors in common. We consider a variant of local edge-colorings wherein the color received by an edge e must be contained in L(e). The locality appears in the function f, i.e., f(x) is some function of the local structure of x in G. Such a notion is a natural generalization of traditional local edge-coloring. Our main results include sufficient conditions on the function f to construct such colorings. As corollaries, we obtain local analogs of Vizing and Shannon's theorems, recovering a recent result of Conley, Grebík and Pikhurko.