CS Paper Radar

Online Graph Coloring: Competitive Ratios Separating Randomized and Deterministic Algorithms

Ken-ichi Kawarabayashi, Hirotaka Yoneda, Masataka Yoneda

cs.DS cs.DMmath.CO ·submitted 2026-11-10 18:58 UTC · v1
theory

Abstract

We study online coloring, focusing on the competitive ratio. The best previously known results were (1) a lower bound of $Ω(n / \log^2 n)$ for both deterministic and randomized algorithms by Halldórsson and Szegedy (1994), (2) an upper bound of $O(n / \log n)$ for randomized algorithms by Halldórsson (1997), and (3) an upper bound of $O(n / \log \log n)$ for deterministic algorithms by Kawarabayashi, Yoneda, and Yoneda (2025). In this paper, we improve these results as follows: 1. A new lower bound of $Ω(n / \log n)$ for deterministic algorithms. 2. A new upper bound of $O(n (\log \log n)^2 / \log^2 n)$ for randomized algorithms. 3. A new upper bound of $O(n / (\log \log n)^{2-\varepsilon})$ for deterministic algorithms for every fixed $\varepsilon>0$. For randomized algorithms, we nearly close the gap between the lower and upper bounds; the remaining gap is only $O((\log \log n)^2)$. We establish the asymptotic separation between randomized and deterministic online graph coloring. Against an oblivious adversary, a polynomial-time randomized algorithm achieves a competitive ratio asymptotically smaller than any deterministic algorithm can guarantee, even with unlimited computation.

Closest papers

Nearest neighbours by meaning across the whole index.

Online Graph Coloring with Random Arrivals

cs.DS cs.DM ·2026-10-16 ·Hirotaka Yoneda, Masataka Yoneda
theory similarity 0.78
Abstract

We study online graph coloring in the random-arrival model, where the vertices are presented in a uniformly random order. Assuming $n$ and $k$ are known in advance, we present a randomized exponential-time 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 that uses a polylogarithmic number of colors for all fixed $k \geq 3$, and is better than a known lower bound of $Ω(\log^{k-1} n)$ colors under adversarial arrivals for all fixed $k \geq 6$. In addition, assuming $n$ is known in advance, we obtain a competitive ratio of $\widetilde{O}(n^{2/3})$. For comparison, it is known to be NP-hard to approximate (offline) graph coloring within a factor of $n^{1-\varepsilon}$ for all fixed $\varepsilon > 0$. Therefore, our exponential-time online algorithm achieves a performance guarantee beyond the NP-hardness threshold for polynomial-time approximation algorithms.

0.14

New bounds for online coloring three-colorable graphs

cs.DS ·2026-10-30 ·Yaqiao Li
theory similarity 0.78
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.

0.21

Fast Distributed $(Δ+ 1)$-Edge Coloring in Bipartite Graphs

cs.DC cs.DS ·2026-10-15 ·Yann Bourreau, Sebastian Brandt, Ananth Narayanan
theoryhot direction similarity 0.74
Abstract

We show that, on bipartite $n$-vertex graphs in the LOCAL model of distributed computation, $(Δ+ 1)$-edge coloring can be solved deterministically in $O(f(Δ) \log n)$ rounds for some function $f$. In particular this implies a deterministic $O(\log n)$-round upper bound for $(Δ+ 1)$-edge coloring on bipartite constant-degree graphs. Our results improve on the previous state-of-the-art bounds (which hold already on general graphs) whose $n$-dependencies are $\widetilde{O}(\log^5 n)$ rounds deterministically and $\widetilde{O}(\log^2 n)$ rounds randomized [Bernshteyn and Dhawan, J.\ Comb.\ Theory 2025]. In fact, we obtain the aforementioned results already for a more restrictive version of $(Δ+ 1)$-edge coloring that corresponds to a \emph{local-palette} strengthening of Vizing's theorem shown recently to hold [Christiansen, STOC 2023]. In this version, every edge $\{u, v\}$ has to be colored with a color from $\{1, \dots, \max(\operatorname{deg}(u), \operatorname{deg}(v))+ 1\}$. For all of our results, the vertices do not need to know on which side of the bipartition they lie---the structural promise of bipartiteness suffices.

0.21

A Tight $\widetilde Ω(\sqrt{m})$ Information-Theoretic Lower Bound for Randomized Online Set Cover

cs.DS ·2026-09-10 ·Ilan Doron-Arad, Joseph, Naor
theory similarity 0.71
Abstract

Online set cover is a fundamental problem in online algorithms, admitting a deterministic $O(\log m\log n)$-competitive algorithm, where $m$ is the number of sets and $n$ is the number of elements. This is essentially tight for deterministic algorithms as well as for polynomial-time randomized algorithms assuming $\mathrm{NP}\not\subseteq\mathrm{BPP}$. However, the best lower bound known for information-theoretic (computationally unlimited) randomized algorithms against an oblivious adversary is only $Ω(\log m)$, whereas the upper bound in terms of $m$ is $O(\sqrt m\log m)=\widetilde O(\sqrt m)$. We prove an $Ω(\sqrt m)$ lower bound for information-theoretic randomized unweighted online set cover, showing that even with unbounded computational power, randomization cannot achieve an $O(\log m)$-competitive ratio. Specifically, our lower bound rules out $O(\log m\cdot\log^{1/2-\varepsilon} n)$-competitive algorithms for every constant $\varepsilon>0$. Our techniques also prove an $Ω(m^{1/3})$ lower bound in the random-order model, and show that every algorithm with $poly(m)$ memory has competitive ratio $Ω(m/\log m)$, even with unlimited computation between requests.

0.25

Improved Space Bounds for Promise Graph Coloring in Adversarial Streams

cs.DS cs.CC ·2026-10-17 ·Sergio Thoumi
theory similarity 0.70
Abstract

We study promise graph coloring in one pass insertion-only adversarial streams. We give a randomized algorithm that distinguishes 3-colorable graphs from graphs that are not 6-colorable using $O(n^{3/2}\log(n/\varepsilon)\log n)$ bits of space. This provides a truly subquadratic space algorithm for a constant coloring gap, answering an open problem posed by Assadi, Sundaresan, and Yazdanyar [SODA 2026] for $q=3$. Combining this algorithm with the vertex-sampling lemma of Assadi et al.\ yields, for any $144\lceil\log_2 n\rceil\le Q\le n$, a one-pass decision algorithm distinguishing $3$-colorable graphs from graphs that are not $Q$-colorable using $O((n/Q)^{3/2}\log^5 n)$ bits of space. This improves upon the $\widetilde{O}((n/Q)^2)$ bound achievable via dynamic streaming techniques. Setting $Q=\lceil n^{1/3}\rceil$ yields a semi-streaming decision algorithm, answering the decision version of another open problem posed by Assadi et al. On the negative side, we prove that distinguishing $χ(G)\le q$ from $χ(G)\ge(q-1)^2$ requires $Ω(n^2/q^5)$ bits of space, improving upon the previously established $q^2/4$ threshold using the same space complexity.

0.19

A Fast Deterministic Algorithm for $(Δ+1)$-edge coloring in CONGEST

cs.DC ·2026-08-19 ·Sebastian Brandt, Ananth Narayanan, Alexandre Nolin
theory similarity 0.69
Abstract

Vizing's theorem states that any graph of maximum degree $Δ$ can be properly edge-colored with $Δ+ 1$ colors (which is optimal in general). A recent breakthrough result by Bernshteyn showed that such a $(Δ+ 1)$-edge coloring can be found deterministically in $poly(Δ,\log n)$ rounds in the LOCAL model of distributed computing, where $n$ denotes the number of vertices of the input graph [J. Comb. Theory 2022]. Since then, the exponent in the $poly(\log n)$-part of the runtime has been improved by Christiansen [STOC 2023] and Bernshteyn and Dhawan [J. Comb. Theory, Series B, 2025]. However, the algorithms used in all of these works use large messages, leaving open the question for efficient algorithms in the more restrictive CONGEST model. We answer this question by presenting the first $poly(Δ,\log n)$-round algorithm for $(Δ+ 1)$-edge coloring in the CONGEST model. Our algorithm is deterministic and the $n$-dependency of its runtime, $\tilde{O}(\log^5 n)$, matches the best published dependency in the LOCAL model.

0.16

FirstFit coloring process of random bipartite graphs and an online coloring lower bound in the random order model

cs.DS cs.DMmath.COmath.PR ·2026-10-11 ·Yaqiao Li, Xin Li
theory similarity 0.68
Abstract

FirstFit colors each arriving vertex with the smallest positive integer absent from its previously colored neighborhood. We prove that this rule can require $n^{Ω(1)}$ many colors on certain bipartite graph of $n$ vertices even when the vertices arrive in a uniformly random order. This refutes the conjecture of Bosek, Gutowski, Lasoń, and Przybyło [BGLP24] that FirstFit uses a polylogarithmic expected number of colors on every bipartite graph in the random order model. We obtain the lower bound by analyzing the FirstFit coloring process on random bipartite graphs, where vertices arrive to either side with equal probability, and with an independent edge density $n^{-x}$ for some $0 < x < 1$. Our result can also be viewed as a qualitative strengthening of Kučera [Kuč91], who showed that, for every $ε> 0$, there are graphs with chromatic number at most $n^ε$ on which FirstFit uses $Ω(n/\log n)$ colors in expectation under a uniformly random order. Our result shows that such poor behavior of FirstFit already occurs for $χ(G) = 2$.

0.27

Streaming Hypergraph Coloring via Palette Sparsification

cs.DM math.COcs.DS ·2026-08-20 ·Artur Czumaj, Pan Peng, Ruizhe Shi, Christian Sohler
theory similarity 0.68
Abstract · 25 pages. This revision merges the original manuscript with independent work by Czumaj, Peng, and Sohler

For every fixed $k\ge2$, we give a randomized one-pass insertion-only algorithm that colors an $n$-vertex $k$-uniform hypergraph of maximum degree $Δ$ with $O(Δ^{1/(k-1)})$ colors using $\widetilde O_k(n)$ bits of working memory. As a graph-theoretic result of independent interest, we also prove a tight palette-sparsification theorem for general uniform hypergraphs. Independently sampled lists of $Θ(\sqrt{\log n})$ colors from a palette of size $O(Δ^{1/(k-1)})$ preserve colorability with high probability; the list-size dependence is asymptotically optimal. These results extend to bounded-rank hypergraphs. We complement the algorithm with a deterministic lower bound: for every fixed polylogarithmic semi-streaming space bound, there are polylogarithmic values of $Δ$ for which any deterministic one-pass algorithm requires $\exp(Δ^{Ω(1)})$ colors.

0.37