Edge-coloring sparse graphs with $Δ$ colors in quasilinear time
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916312944476160 |
|---|---|
| author | Kowalik, Lukasz |
| author_facet | Kowalik, Lukasz |
| contents | In this paper we show that every graph $G$ of bounded maximum average degree ${\rm mad}(G)$ and with maximum degree $Δ$ can be edge-colored using the optimal number of $Δ$ colors in quasilinear time, whenever $Δ\ge 2{\rm mad}(G)$. The maximum average degree is within a multiplicative constant of other popular graph sparsity parameters like arboricity, degeneracy or maximum density. Our algorithm extends previous results of Chrobak and Nishizeki [J. Algorithms, 1990] and Bhattacharya, Costa, Panski and Solomon [ESA 2024]. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_13839 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Edge-coloring sparse graphs with $Δ$ colors in quasilinear time Kowalik, Lukasz Data Structures and Algorithms In this paper we show that every graph $G$ of bounded maximum average degree ${\rm mad}(G)$ and with maximum degree $Δ$ can be edge-colored using the optimal number of $Δ$ colors in quasilinear time, whenever $Δ\ge 2{\rm mad}(G)$. The maximum average degree is within a multiplicative constant of other popular graph sparsity parameters like arboricity, degeneracy or maximum density. Our algorithm extends previous results of Chrobak and Nishizeki [J. Algorithms, 1990] and Bhattacharya, Costa, Panski and Solomon [ESA 2024]. |
| title | Edge-coloring sparse graphs with $Δ$ colors in quasilinear time |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2401.13839 |