Online Edge Coloring via Tree Recurrences and Correlation Decay
- Janardhan (Jana) Kulkarni ,
- Yang Liu ,
- Yang Liu ,
- Yang Liu ,
- Ashwin Sah ,
- Mehtaab Sawhney ,
- Jakub Tarnawski
We give an online algorithm that with high probability computes a \(({e \over e−1} + o(1))Δ\) edge coloring on a graph \(G\) with maximum degree \(Δ=ω(log n)\) under online edge arrivals against oblivious adversaries, making first progress on the conjecture of Bar-Noy, Motwani, and Naor in this general setting. Our algorithm is based on reducing to a matching problem on locally treelike graphs, and then applying a tree recurrences based approach for arguing correlation decay.