Radu Vintan

SODA Conference 2025 Conference Paper

Deterministic Online Bipartite Edge Coloring

• Joakim Blikstad
• Ola Svensson
• Radu Vintan
• David Wajc

FOCS Conference 2025 Conference Paper

Online Edge Coloring: Sharp Thresholds

• Joakim Blikstad
• Ola Svensson
• Radu Vintan
• David Wajc

Vizing’s theorem guarantees that every graph with maximum degree $\Delta$ admits an edge coloring using $\Delta+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 \Delta-1$ colors. Over thirty years ago, Bar-Noy, Motwani, and Naor [IPL’92] proved that this guarantee is optimal among deterministic algorithms when $\Delta=O(\log n)$, and among randomized algorithms when $\Delta=O(\sqrt{\log n})$. While deterministic improvements seemed out of reach, they conjectured that for graphs with $\Delta=\omega(\log n)$, randomized algorithms can achieve $(1+o(1)) \Delta$ edge coloring. This conjecture was recently resolved in the affirmative: a $(1+o(1)) \Delta$ coloring is achievable online using randomization for all graphs with $\Delta=\omega(\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)) \Delta$-colorings for all $\Delta=\omega(\log n)$. Second, we give a randomized algorithm achieving $(1+o(1)) \Delta$ colorings already when $\Delta=\omega(\sqrt{\log n})$. Our results establish sharp thresholds for when greedy can be surpassed, and nearoptimal guarantees can be achieved - matching the impossibility results of [BNMN IPL’92], both deterministically and randomly.

STOC Conference 2024 Conference Paper

Online Edge Coloring Is (Nearly) as Easy as Offline

• Joakim Blikstad
• Ola Svensson
• Radu Vintan
• David Wajc

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).