arXiv preprint ·
An $O(n^{0.1537})$-Coloring Algorithm for 3-Colorable Graphs
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
We present a polynomial-time randomized algorithm that colors every $n$-vertex $3$-colorable graph with $O(n^{0.1537})$ colors. This improves upon the previous bound of $O(n^{0.1954})$ colors by Bansal, Huang, and Lee (SODA '27). To achieve this result, we introduce a new algorithmic framework for finding a large independent set from a solution to the vector coloring SDP. Combined with the (combinatorial) dense-progress algorithm of Kawarabayashi, Thorup, and Yoneda (STOC '24), this framework yields an $n^{1/6 + o(1)}$-coloring algorithm. Furthermore, we strengthen the SDP-based algorithm specifically for 3-colorable graphs to achieve $O(n^{0.1537})$ colors.
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
Coordinating Boundaries: Improved Approximation Algorithms for Unweighted Non-Preemptive Throughput Maximization
An Unconditional Space-Approximation Lower Bound for Semi-Streaming Matching
The Complexity of Value Optimization in Sporadic Task Systems
Uniformity Testing for the Monomer-Dimer Model
Linear Hashing Is Poissonesque
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.