Online Edge Coloring: Sharp Thresholds
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912508178071552 |
|---|---|
| author | Blikstad, Joakim Svensson, Ola Vintan, Radu Wajc, David |
| author_facet | Blikstad, Joakim Svensson, Ola Vintan, Radu Wajc, David |
| contents | Vizing's theorem guarantees that every graph with maximum degree $Δ$ admits an edge coloring using $Δ+ 1$ colors. In online settings - where edges arrive one at a time and must be colored immediately - a simple greedy algorithm uses at most $2Δ- 1$ colors. Over thirty years ago, Bar-Noy, Motwani, and Naor [IPL'92] proved that this guarantee is optimal among deterministic algorithms when $Δ= O(\log n)$, and among randomized algorithms when $Δ= O(\sqrt{\log n})$. While deterministic improvements seemed out of reach, they conjectured that for graphs with $Δ= ω(\log n)$, randomized algorithms can achieve $(1 + o(1))Δ$ edge coloring. This conjecture was recently resolved in the affirmative: a $(1 + o(1))Δ$-coloring is achievable online using randomization for all graphs with $Δ= ω(\log n)$ [BSVW STOC'24].
Our results go further, uncovering two findings not predicted by the original conjecture. First, we give a deterministic online algorithm achieving $(1 + o(1))Δ$-colorings for all $Δ= ω(\log n)$. Second, we give a randomized algorithm achieving $(1 + o(1))Δ$-colorings already when $Δ= ω(\sqrt{\log n})$. Our results establish sharp thresholds for when greedy can be surpassed, and near-optimal guarantees can be achieved - matching the impossibility results of [BNMN IPL'92], both deterministically and randomly. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_21560 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Online Edge Coloring: Sharp Thresholds Blikstad, Joakim Svensson, Ola Vintan, Radu Wajc, David Data Structures and Algorithms Vizing's theorem guarantees that every graph with maximum degree $Δ$ admits an edge coloring using $Δ+ 1$ colors. In online settings - where edges arrive one at a time and must be colored immediately - a simple greedy algorithm uses at most $2Δ- 1$ colors. Over thirty years ago, Bar-Noy, Motwani, and Naor [IPL'92] proved that this guarantee is optimal among deterministic algorithms when $Δ= O(\log n)$, and among randomized algorithms when $Δ= O(\sqrt{\log n})$. While deterministic improvements seemed out of reach, they conjectured that for graphs with $Δ= ω(\log n)$, randomized algorithms can achieve $(1 + o(1))Δ$ edge coloring. This conjecture was recently resolved in the affirmative: a $(1 + o(1))Δ$-coloring is achievable online using randomization for all graphs with $Δ= ω(\log n)$ [BSVW STOC'24]. Our results go further, uncovering two findings not predicted by the original conjecture. First, we give a deterministic online algorithm achieving $(1 + o(1))Δ$-colorings for all $Δ= ω(\log n)$. Second, we give a randomized algorithm achieving $(1 + o(1))Δ$-colorings already when $Δ= ω(\sqrt{\log n})$. Our results establish sharp thresholds for when greedy can be surpassed, and near-optimal guarantees can be achieved - matching the impossibility results of [BNMN IPL'92], both deterministically and randomly. |
| title | Online Edge Coloring: Sharp Thresholds |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2507.21560 |