Papers › Sublinear Algorithms for (Δ+ 1) Vertex Coloring
Sublinear Algorithms for (Δ+ 1) Vertex Coloring
Sepehr Assadi, Yu Chen, Sanjeev Khanna
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
Any graph with maximum degree Δ admits a proper vertex coloring with Δ+ 1 colors that can be found via a simple sequential greedy algorithm in linear time and space. But can one find such a coloring via a sublinear algorithm? We answer this fundamental question in the affirmative for several canonical classes of sublinear algorithms including graph streaming, sublinear time, and massively parallel computation (MPC) algorithms. In particular, we design: * A single-pass semi-streaming algorithm in dynamic streams using Õ(n) space. The only known semi-streaming algorithm prior to our work was a folklore O(log n)-pass algorithm obtained by simulating classical distributed algorithms in the streaming model. * A sublinear-time algorithm in the standard query model that allows neighbor queries and pair queries using Õ(n√(n)) time. We further show that any algorithm that outputs a valid coloring with sufficiently large constant probability requires Ω(n√(n)) time. No non-trivial sublinear time algorithms were known prior to our work. * A parallel algorithm in the massively parallel computation (MPC) model using Õ(n) memory per machine and O(1) MPC rounds. Our number of rounds significantly improves upon the recent O(loglogΔ·log^*(n))-round algorithm of Parter [ICALP 2018]. At the core of our results is a remarkably simple meta-algorithm for the (Δ+1) coloring problem: Sample O(logn) colors for each vertex from the Δ+1 colors; find a proper coloring of the graph using only the sampled colors. We prove that the sampled set of colors with high probability contains a proper coloring of the input graph. The sublinear algorithms are then obtained by designing efficient algorithms for finding a proper coloring of the graph from the sampled colors in the corresponding models.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections