{"ID":2889082,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.21560","arxiv_id":"2507.21560","title":"Online Edge Coloring: Sharp Thresholds","abstract":"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.","short_abstract":"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] prov...","url_abs":"https://arxiv.org/abs/2507.21560","url_pdf":"https://arxiv.org/pdf/2507.21560v1","authors":"[\"Joakim Blikstad\",\"Ola Svensson\",\"Radu Vintan\",\"David Wajc\"]","published":"2025-07-29T07:51:27Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}