Informace o publikaci
Local version of Vizing's theorem for multigraphs
| Autoři | |
|---|---|
| Rok publikování | 2024 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | JOURNAL OF GRAPH THEORY |
| Fakulta / Pracoviště MU | |
| Citace | |
| www | https://onlinelibrary.wiley.com/doi/full/10.1002/jgt.23155 |
| Doi | https://doi.org/10.1002/jgt.23155 |
| Klíčová slova | edge colouring; local colouring; multigraphs; Vizing's theorem |
| Popis | Extending a result of Christiansen, we prove that every multigraph G = ( V , E ) $G=(V,E)$ admits a proper edge colouring ? : E ? { 1 , 2 , ? } $\phi :E\to \{1,2,\ldots \,\}$ which is local, that is, ? ( e ) ? max { d ( x ) + ? ( x ) , d ( y ) + ? ( y ) } $\phi (e)\leqslant \max \{d(x)+\pi (x),d(y)+\pi (y)\}$ for every edge e $e$ with end-points x , y ? V $x,y\in V$, where d ( z ) $d(z)$ (resp. ? ( z ) $\pi (z)$) denotes the degree of a vertex z $z$ (resp. the maximum edge multiplicity at z $z$). This is derived from a local version of the Fan Equation. |