List coloring uncrowded hypergraphs at the shattering threshold
Abstract
Improving an earlier bound of Frieze and Mubayi, Iliopoulos showed that any k-uniform uncrowded hypergraph of maximum degree Δ has list chromatic number at most (1+o(1))(k−1)(Δ/logΔ)1/(k−1). Determining the optimal leading constant in this bound remains a major open problem. A natural target for the constant, suggested by the coupon-collector heuristic, is (k−1)1/(k−1), which also arises independently as the shattering threshold for coloring and finding large independent sets in sparse random hypergraphs. We show that uncrowded hypergraphs attain this threshold: for k ≥ 2, every k-uniform uncrowded hypergraph ℋ of maximum degree at most Δ satisfies χℓ(ℋ)≤(1+o(1))((k−1)Δ/logΔ)1/(k−1). This matches the coupon-collector heuristic, and establishes a 2019 conjecture of Molloy for uncrowded hypergraphs. As a consequence, we show that every k-uniform linear hypergraph of maximum degree at most Δ has chromatic number at most ck(Δ/(log Δ))1/(k−1) with ck=1−ok(1), resolving, in a stronger form, a recent conjecture of Verstraëte and Wilson on the independence number of linear hypergraphs. Our techniques yield the first palette sparsification result for hypergraph coloring using o(Δ1/(k−1)) colors per vertex. Specifically, for an uncrowded k-graph ℋ and q=Θ((Δ/γlogΔ)1/(k−1)), sampling Θ(Δγ/(k−1)) colors per vertex suffices to obtain a proper q-coloring of ℋ w.h.p. As an algorithmic consequence, we obtain a single-pass streaming algorithm using O(n1+o(1)) space for uncrowded k-graphs, and, via hypergraph partitioning, for linear hypergraphs as well.
Related
- Random independent sets in uncrowded hypergraphs
- List 3-Coloring in tame classes of graphs in quasipolynomial time
- Double-Partition Coloring problem: a unified approach for conflict-free coloring of hypergraphs and other coloring problems in graphs
- List coloring C3-free planar graphs with a sparse matching of restricted lists
- Sufficiency of Hall's Condition for Graphic List Coloring
BibTeX
@misc{dhawan2026list,
title = {{List coloring uncrowded hypergraphs at the shattering threshold}},
author = {Abhishek Dhawan and Abhishek Methuku and Minh-Quan Vo},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2606.18048},
eprint = {2606.18048},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2606.18048},
}
RIS
TY - UNPB
TI - List coloring uncrowded hypergraphs at the shattering threshold
AU - Abhishek Dhawan
AU - Abhishek Methuku
AU - Minh-Quan Vo
PY - 2026
DA - 2026/10/24
PB - arXiv
DO - 10.48550/arxiv.2606.18048
UR - https://arxiv.org/abs/2606.18048
AB - Improving an earlier bound of Frieze and Mubayi, Iliopoulos showed that any k-uniform uncrowded hypergraph of maximum degree Δ has list chromatic number at most (1+o(1))(k−1)(Δ/logΔ)^1/(k−1). Determining the optimal leading constant in this bound remains a major open problem. A natural target for the constant, suggested by the coupon-collector heuristic, is (k−1)^1/(k−1), which also arises independently as the shattering threshold for coloring and finding large independent sets in sparse random hypergraphs. We show that uncrowded hypergraphs attain this threshold: for k ≥ 2, every k-uniform uncrowded hypergraph ℋ of maximum degree at most Δ satisfies χ_ℓ(ℋ)≤(1+o(1))((k−1)Δ/logΔ)^1/(k−1). This matches the coupon-collector heuristic, and establishes a 2019 conjecture of Molloy for uncrowded hypergraphs. As a consequence, we show that every k-uniform linear hypergraph of maximum degree at most Δ has chromatic number at most c_k(Δ/(log Δ))^1/(k−1) with c_k=1−o_k(1), resolving, in a stronger form, a recent conjecture of Verstraëte and Wilson on the independence number of linear hypergraphs. Our techniques yield the first palette sparsification result for hypergraph coloring using o(Δ^1/(k−1)) colors per vertex. Specifically, for an uncrowded k-graph ℋ and q=Θ((Δ/γlogΔ)^1/(k−1)), sampling Θ(Δ^γ/(k−1)) colors per vertex suffices to obtain a proper q-coloring of ℋ w.h.p. As an algorithmic consequence, we obtain a single-pass streaming algorithm using O(n^1+o(1)) space for uncrowded k-graphs, and, via hypergraph partitioning, for linear hypergraphs as well.
ER -