Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | https://arxiv.org/abs/2306.04173 |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914779662123008 |
|---|---|
| author | Conley, Clinton T. Grebik, Jan Pikhurko, Oleg |
| author_facet | Conley, Clinton T. Grebik, Jan Pikhurko, Oleg |
| contents | Extending a result of Christiansen, we prove that every mutli-graph $G=(V,E)$ admits a proper edge colouring $ϕ:E\to \{1,2,\dots\}$ which is local, that is, $ϕ(e)\le \max\{d(x)+π(x),d(y)+π(y)\}$ for every edge $e$ with end-points $x,y\in V$, where $d(z)$ (resp.\ $π(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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2306_04173 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Local version of Vizing's theorem for multi-graphs Conley, Clinton T. Grebik, Jan Pikhurko, Oleg Combinatorics Extending a result of Christiansen, we prove that every mutli-graph $G=(V,E)$ admits a proper edge colouring $ϕ:E\to \{1,2,\dots\}$ which is local, that is, $ϕ(e)\le \max\{d(x)+π(x),d(y)+π(y)\}$ for every edge $e$ with end-points $x,y\in V$, where $d(z)$ (resp.\ $π(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. |
| title | Local version of Vizing's theorem for multi-graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2306.04173 |