Online Edge Coloring via Tree Recurrences and Correlation Decay

.We give an online algorithm that with high probability computes a \( (e/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 recurrence based approach for arguing correlation decay.Keywordsedge coloringonline algorithmstree recurrencescorrelation decayMSC codes68W2768R01