Back to Search Start Over

Local version of Vizing's theorem for multi-graphs

Authors :
Conley, Clinton T.
Grebik, Jan
Pikhurko, Oleg
Publication Year :
2023

Abstract

Extending a result of Christiansen, we prove that every mutli-graph $G=(V,E)$ admits a proper edge colouring $\phi:E\to \{1,2,\dots\}$ which is local, that is, $\phi(e)\le \max\{d(x)+\pi(x),d(y)+\pi(y)\}$ for every edge $e$ with end-points $x,y\in V$, 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.<br />Comment: 10 pages, minor revision

Subjects

Subjects :
Mathematics - Combinatorics

Details

Database :
arXiv
Publication Type :
Report
Accession number :
edsarx.2306.04173
Document Type :
Working Paper