Beyond Brooks: $(Δ-1)$-Coloring in Semi-Streaming
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914544872325120 |
|---|---|
| author | Flin, Maxime Halldórsson, Magnús M. |
| author_facet | Flin, Maxime Halldórsson, Magnús M. |
| contents | Reed [J.~Comb.~Theory B, 1999] showed that graphs of maximum degree $Δ\geq 10^{14}$ without $Δ$-cliques are $(Δ-1)$-colorable. We design a one-pass semi-streaming algorithm for computing such a coloring. Additionally, we prove that any one-pass $(Δ-k)$-coloring algorithm for $0\leq k < (Δ+1)/2$ requires $Ω(n(k+1))$ space. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_07774 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Beyond Brooks: $(Δ-1)$-Coloring in Semi-Streaming Flin, Maxime Halldórsson, Magnús M. Data Structures and Algorithms Reed [J.~Comb.~Theory B, 1999] showed that graphs of maximum degree $Δ\geq 10^{14}$ without $Δ$-cliques are $(Δ-1)$-colorable. We design a one-pass semi-streaming algorithm for computing such a coloring. Additionally, we prove that any one-pass $(Δ-k)$-coloring algorithm for $0\leq k < (Δ+1)/2$ requires $Ω(n(k+1))$ space. |
| title | Beyond Brooks: $(Δ-1)$-Coloring in Semi-Streaming |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2605.07774 |