Hat guessing number bounded by degeneracy

Informal Belief on Degeneracy Bound for Hat Guessing Number · arXiv:2107.05995

arXiv Informal medium confidence— first stated 2021-07-21

Authors: Noga Alon, Jeremy Chizewer

Status open high confidence

The conjecture that there exists f : N → N with HG(G) ≤ f(d) for every d-degenerate graph G remains open. The closest follow-up (arXiv:2112.09619, SIAM JDM 2023) introduces a stronger graph parameter called strong degeneracy and proves HG(G) is bounded above by a function of strong degeneracy—notably reducing the upper bound for outerplanar graphs from ~2^125000 down to 40—but explicitly leaves the question for standard degeneracy open. Prior work (arXiv:2003.04990, E-JC 2020, predating this paper) established doubly-exponential lower bounds HG(G) ≥ 2^(2^(d-1)) for d-degenerate graphs, but this does not preclude a bounding function existing.

Cited literature (1)

partial Hat guessing numbers of strongly degenerate graphs (2023)

see arXiv:2112.09619 · SIAM Journal on Discrete Mathematics · arXiv:2112.09619 · doi:10.1137/22M1479154

Proves HG(G) is bounded above by a function of strong degeneracy (a parameter stronger than degeneracy), reducing the outerplanar upper bound to 40, but explicitly leaves open whether HG(G) is bounded by a function of standard degeneracy.

Reviewer notes. The conjecture is explicitly discussed as open in arXiv:2112.09619. The doubly-exponential lower bounds from arXiv:2003.04990 (E-JC 2020) predate the source paper. A separate line of work (arXiv:2301.10305) shows the hat guessing number of some planar graph is at least 22, meaning f(5) ≥ 22 if the conjecture holds, but this does not resolve the conjecture. No resolution found in 2022–2026 literature.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Informal. It seems plausible that there exists a function $f : \mathbb{N} \to \mathbb{N}$ such that for every $d$-degenerate graph $G$, $\mathrm{HG}(G) \leq f(d)$.

Context

The authors remark in the open problems section that such a bounding function seems plausible, noting that it would imply absolute constant bounds on the hat guessing number of planar graphs (which are $5$-degenerate) and a Hadwiger-number bound via degeneracy results.

Source paper

On the Hat Guessing Number of Graphs
Noga Alon, Jeremy Chizewer · 2021-07-21
https://arxiv.org/abs/2107.05995 PDF source