arXiv preprint ·
New bounds for online coloring three-colorable graphs
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
We prove new lower and upper bounds for online coloring of three-colorable graphs, improving classical bounds of Vishwanathan [FOCS'1990] that have stood for more than three decades. For the lower bound against deterministic algorithms, we improve Vishwanathan's $Ω(\log^2n)$ to \(\exp\!\bigl(Ω((\log n)^{1/3}(\log\log n)^{2/3})\bigr)\). For the upper bound of randomized algorithms, we give a randomized algorithm that achieves $O(\sqrt{n})$ improving Vishwanathan's $O(\sqrt{n \log n})$. Technically, for the lower bound construction, we introduce the language of $t$-fold coloring for simpler description of recursive construction, and the notion of post-degree for future control, and use the flexibility of two-sided colors of bipartite graph, constructed using the independent set amplification method of Vishwanathan, as building blocks to ensure three-colorability. The randomized algorithm integrates, in a new way, some of the ideas in offline coloring of Wigderson and Blum with ideas of Vishwanathan in the online setting, such as the degree control from Wigderson, the offline-monochromatic class from Blum, and the anchor-sampling from Vishwanathan and the CBIP algorithm by Lov{á}sz, Saks and Trotter.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
The Competitive Ratio of Online Budgeted Allocation is Strictly Smaller than $1-1/e$
Limits and Constants of OpenAI's Claimed ETH Refutation
Traveling Salesman Problem on Graphs with Proportional Independent Set
Facility Location with Customer Incompatibilities
Multiple Swap Local Search Approximations for Uniform-Cost Capacitated Facility Location with Extensions to Outliers
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.