CS Paper Radar

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

Amey Bhangale, Krishna Priya KM, Simon Rubin-Toles

cs.CC ·submitted 2026-10-27 19:14 UTC · v1
hot direction

Abstract

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.

Comment
20 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Almost All 3-uniform Hypergraphs are Class 1

cs.DM math.CO ·2026-11-03 ·Arnab Chaterjee, Asaf Ferber, Marcelo Sales, Mason Shurman
similarity 0.75
Abstract

The chromatic index $χ'(H)$ of a hypergraph $H$ is the smallest number of colors needed to color its edges so that no two adjacent edges share the same color. The chromatic index is trivially bounded below by the maximum degree $Δ(H)$, and when $χ'(H)= Δ(H)$, we say that $H$ is Class 1. It is well known that almost every 2-graph is Class 1, and we extend this result to 3-graphs. We show for $n^{-2/3-1/200}\leq p \leq 0.99$ that the $3$-uniform binomial random hypergraph $H\sim H_{n,p}^{(3)}$ is Class 1 with high probability. We also show that this result doesn't hold for uniformities above $3$. For a broad range of $p$, when $k \geq 4$ and $k \nmid n$, the hypergraph $H \sim H_{n,p}^{(k)}$ is with high probability not Class 1.

0.16

New bounds for online coloring three-colorable graphs

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

Online Graph Coloring with Random Arrivals

cs.DS cs.DM ·2026-10-16 ·Hirotaka Yoneda, Masataka Yoneda
theory similarity 0.73
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

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

Property B for random non-uniform hypergraphs

cs.DM math.COmath.PR ·2026-10-05 ·Grzegorz Ryn, Jakub Kozik
similarity 0.70
Abstract

We show that, in random hypergraphs with several permitted edge sizes, non-uniformity affects existential and algorithmic bounds for 2-colorability (Property B) in fundamentally different ways. Assigning weight $2^{-k}$ to each $k$-edge, we obtain upper and lower bounds in terms of the total edge weight that asymptotically match the uniform bounds as the minimum permitted edge size grows, regardless of how edges are distributed among sizes. We also extend the best-known algorithm for 2-coloring random uniform hypergraphs to the non-uniform setting. With weight $\frac{k}{2^k}$ assigned to each $k$-edge, we construct non-uniform instances whose expected total edge weight per vertex is arbitrarily large, yet the algorithm finds a proper coloring asymptotically almost surely. In the uniform setting, the algorithm fails with high probability once this quantity exceeds a constant. Our construction uses sufficiently separated edge sizes, so that edges of different sizes become relevant at well-separated stages of the execution and their effects are essentially independent.

0.16

An Improved Bound for Testing $k$-Colorability

cs.DM ·2026-10-22 ·Bangjie Xu
theory similarity 0.70
Abstract

We study the sample complexity of testing $k$-colorability in the dense graph model. A graph is $\varepsilon$-far from being $k$-colorable if at least $\varepsilon n^2$ edge deletions are required to make it $k$-colorable. We prove that a uniformly random induced subgraph on $O(k\log k/\varepsilon)$ vertices is non-$k$-colorable with probability at least $2/3$ whenever the original graph is $\varepsilon$-far from $k$-colorable. The proof combines a palette-based coloring process with a container-style encoding-and-reconstruction argument. This yields $O(k\log k/\varepsilon)$, which is no worse than the previous state of the art $O(k\log (1/\varepsilon)/\varepsilon)$ throughout the nonvacuous parameter range, and is an improvement when $\log k=o(\log(1/\varepsilon))$. For each fixed $k$, combining this upper bound with the known $Ω(\log k/\varepsilon)$ lower bound gives $Θ(1/\varepsilon)$ dependence on $\varepsilon$.

0.06

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

A proof of a conjecture on bipartite correspondence packing

cs.DM math.CO ·2026-11-16 ·Xin Zhang
theory similarity 0.69
Abstract

A correspondence cover assigns a set of possible colors to each vertex of a graph. For each edge, a matching between the two endpoint color sets specifies the forbidden color pairs. A correspondence coloring selects one color at each vertex so that no forbidden pair is selected. A full correspondence packing is a collection of such colorings that uses every color at each vertex exactly once. We prove a conjecture of Cambie, Cames van Batenburg, Davies, and Kang [Random Structures & Algorithms 64 (2024), 62--93]. For every sufficiently large $D$, there is a positive integer $k(D)=(1+o(1))D/\log D$ such that every correspondence cover of any finite bipartite graph has a full correspondence packing if each color has at most $D$ forbidden partners and each vertex has $k(D)$ colors. More precisely, we prove this conclusion with \[ k(D)=\left\lceil\frac{D}{\log D-2\log\log D-6}\right\rceil \] for every integer $D\ge\lceil e^{20}\rceil$.

0.21