Online edge coloring via tree recurrences and correlation decay

DOI10.1145/3519935.3519986arXiv2111.00721OpenAlexW3214604542MaRDI QIDQ6083466

Author name not available (Why is that?)

Publication date: 8 December 2023

Published in: (Search for Journal in Brave)

Abstract: We give an online algorithm that with high probability computes a $left(fracee-1+o(1)ight)Delta$ edge coloring on a graph $G$ with maximum degree $Delta=omega(logn)$ 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.

Full work available at URL: https://arxiv.org/abs/2111.00721

zbMATH Keywords

No records found.

Mathematics Subject Classification ID

No records found.

This page was built for publication: Online edge coloring via tree recurrences and correlation decay

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6083466)