CS Paper Radar

New bounds for online coloring three-colorable graphs

Yaqiao Li

cs.DS ·submitted 2026-10-30 10:07 UTC · v1
theory

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.

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.80
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

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.79
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

Improved Space Bounds for Promise Graph Coloring in Adversarial Streams

cs.DS cs.CC ·2026-10-17 ·Sergio Thoumi
theory similarity 0.78
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

Online Graph Coloring: Competitive Ratios Separating Randomized and Deterministic Algorithms

cs.DS cs.DMmath.CO ·2026-11-10 ·Ken-ichi Kawarabayashi, Hirotaka Yoneda, Masataka Yoneda
theory similarity 0.78
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.

0.18

Coloring 3-colorable graphs with $O(n^{4/23})$ colors via a Gaussian-cover recursion

cs.DS cs.CCcs.DMmath.CO ·2026-10-01 ·Emile Anand
theory similarity 0.77
Abstract · 29 pages, 1 figure

We give a randomized polynomial-time algorithm that colors any promised $3$-colorable graph on $n$ vertices with $\smash{O(n^{4/23}) = O(n^{0.17391\ldots})}$ colors, improving on the recent bounds of $O(n^{0.19539})$ by Bansal, Huang, and Lee and Narang and Tang who obtained $O(n^{(13-\sqrt{97})/18+ε})=O(n^{0.17506\dots + ε})$ colors for every fixed $\smash{ε>0}$. To prove our result, we start from a fixed-level semidefinite relaxation, where we use a finite-depth recursion on Gaussian covers. Fixing a root vertex, we group vertices by correlation with the root vector. Here, each step extends a cover of directions by one edge and transfers it to a successor group. Our key analytic ingredient is a variance bound for Gaussian maxima: for a maximum of $m\geq 2$ centered linear forms with coefficient norms at most $r$, mean $μ$, and variance $v$, we prove $v\leq r^2-μ^2/(2\log m)$ using Chen's Gaussian convexity theorem. Together with a variance-scale lower-tail estimate, this controls the threshold loss at each extension, which shows that root-conditioned vector colorings can either extract a large independent set from a group or bound its size, forcing a contradiction after constantly many steps. The resulting sparse-case guarantee combines with the dense progress bound of Kawarabayashi, Thorup, and Yoneda, and the recursion's numerical inequalities are verified via rational interval arithmetic.

0.08

An $O(n^{0.1537})$-Coloring Algorithm for 3-Colorable Graphs

cs.DS ·2026-10-26 ·Kaisei Deguchi, Ken-ichi Kawarabayashi, Hirotaka Yoneda, Masataka Yoneda
similarity 0.77
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.

0.19

Hardness of Coloring $2$-Colorable $3$-Uniform Hypergraphs with $\log^{Ω(1)} n$ Colors

cs.CC ·2026-10-27 ·Amey Bhangale, Krishna Priya KM, Simon Rubin-Toles
hot direction similarity 0.75
Abstract · 20 pages

We show that it is quasi-NP-hard to color a $2$-colorable $3$-uniform hypergraph on $n$ vertices using $O((\log n)^{1/8})$ colors. This exponentially improves the result of Dinur, Regev, and Smyth [Combinatorica'2005], which showed it is quasi-NP-hard to color a $2$-colorable $3$-uniform hypergraph on $n$ vertices using $O((\log \log n)^{1/3})$ colors.

0.26

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.74
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