Online Edge Coloring is (Nearly) as Easy as Offline
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914694575423488 |
|---|---|
| author | Blikstad, Joakim Svensson, Ola Vintan, Radu Wajc, David |
| author_facet | Blikstad, Joakim Svensson, Ola Vintan, Radu Wajc, David |
| contents | The classic theorem of Vizing (Diskret. Analiz.'64) asserts that any graph of maximum degree $Δ$ can be edge colored (offline) using no more than $Δ+1$ colors (with $Δ$ being a trivial lower bound). In the online setting, Bar-Noy, Motwani and Naor (IPL'92) conjectured that a $(1+o(1))Δ$-edge-coloring can be computed online in $n$-vertex graphs of maximum degree $Δ=ω(\log n)$. Numerous algorithms made progress on this question, using a higher number of colors or assuming restricted arrival models, such as random-order edge arrivals or vertex arrivals (e.g., AGKM FOCS'03, BMM SODA'10, CPW FOCS'19, BGW SODA'21, KLSST STOC'22). In this work, we resolve this longstanding conjecture in the affirmative in the most general setting of adversarial edge arrivals. We further generalize this result to obtain online counterparts of the list edge coloring result of Kahn (J. Comb. Theory. A'96) and of the recent "local" edge coloring result of Christiansen (STOC'23). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_18339 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Online Edge Coloring is (Nearly) as Easy as Offline Blikstad, Joakim Svensson, Ola Vintan, Radu Wajc, David Data Structures and Algorithms The classic theorem of Vizing (Diskret. Analiz.'64) asserts that any graph of maximum degree $Δ$ can be edge colored (offline) using no more than $Δ+1$ colors (with $Δ$ being a trivial lower bound). In the online setting, Bar-Noy, Motwani and Naor (IPL'92) conjectured that a $(1+o(1))Δ$-edge-coloring can be computed online in $n$-vertex graphs of maximum degree $Δ=ω(\log n)$. Numerous algorithms made progress on this question, using a higher number of colors or assuming restricted arrival models, such as random-order edge arrivals or vertex arrivals (e.g., AGKM FOCS'03, BMM SODA'10, CPW FOCS'19, BGW SODA'21, KLSST STOC'22). In this work, we resolve this longstanding conjecture in the affirmative in the most general setting of adversarial edge arrivals. We further generalize this result to obtain online counterparts of the list edge coloring result of Kahn (J. Comb. Theory. A'96) and of the recent "local" edge coloring result of Christiansen (STOC'23). |
| title | Online Edge Coloring is (Nearly) as Easy as Offline |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2402.18339 |