Local version of Vizing's theorem for multi-graphs

arXiv2306.04173MaRDI QIDQ6439474FDOQ6439474

Authors: Clinton T. Conley, Jan Grebík, Oleg Pikhurko 

Publication date: 7 June 2023

Abstract: Extending a result of Christiansen, we prove that every mutli-graph $G=(V,E)$ admits a proper edge colouring $phi:Eo1,2,dots$ which is local, that is, $phi(e)lemaxd(x)+pi(x),d(y)+pi(y)$ for every edge $e$ with end-points $x,yinV$, where $d(z)$ (resp. $pi(z)$) denotes the degree of a vertex $z$ (resp. the maximum edge multiplicity at $z$). This is derived from a local version of the Fan Equation.

This page was built for publication: Local version of Vizing's theorem for multi-graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6439474)