Online Graph Coloring with Random Arrivals
In the authors' words
We study online graph coloring in the random-arrival model, where the vertices are presented in a uniformly random order. Assuming and are known in advance, we present a randomized exponential-time algorithm that colors any -colorable graph on vertices with colors in expectation. This is the first online coloring algorithm that uses a polylogarithmic number of colors for all fixed , and is better than a known lower bound of colors under adversarial arrivals for all fixed . In addition, assuming is known in advance, we obtain a competitive ratio of . For comparison, it is known to be NP-hard to approximate (offline) graph coloring within a factor of for all fixed . Therefore, our exponential-time online algorithm achieves a performance guarantee beyond the NP-hardness threshold for polynomial-time approximation algorithms.
In plain words AI summary
The authors study online graph coloring where vertices arrive in random order. They present a randomized algorithm that colors any k-colorable graph on n vertices with O(k^3 log^2 k log^4 n) colors in expectation. This is the first online coloring algorithm using a polylogarithmic number of colors for all fixed k at least 3. Their exponential-time online algorithm achieves a performance guarantee beyond the NP-hardness threshold for polynomial-time approximation algorithms.
Written by Kimi K2.5 using only the abstract above. Jev checked that every sentence is supported by the abstract sentences it cites, and removed any that were not. Point at a sentence to highlight its source.
Appeared: Monday, October 19. arXiv. Preprint, not yet peer-reviewed.