Hat guessing number under universal vertex addition

Problem on Hat Guessing Number After Adding a Universal Vertex · arXiv:2107.05995

arXiv Problem high confidence— first stated 2021-07-21

Authors: Noga Alon, Jeremy Chizewer

Status open medium confidence

No follow-up paper was found that establishes a general upper bound for HG(G') in terms of HG(G) when G' is obtained by adding a universal vertex to G, nor one that proves no such function exists. The source paper itself shows the gap can be large (HG(G') can reach q^2+q where q = HG(G)), so any bounding function must grow at least quadratically. Searches across arXiv and related literature on hat guessing numbers (including papers on degenerate graphs, random graphs, and proper colorings) found no subsequent resolution of this specific problem as of May 2026.

Reviewer notes. No follow-up found in 5 web calls. The problem dates from 2021; absence of resolution after ~5 years lowers confidence slightly below high. Related active literature (degenerate graphs, random graphs, proper colorings) does not address the universal vertex addition problem. The lower bound q^2 <= HG(G') is implicit in the source paper via the G_d(N) construction.

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

Problem. Establish an upper bound for $\mathrm{HG}(G')$ as a function of $\mathrm{HG}(G)$, where $G'$ is obtained from $G$ by adding a single vertex connected to all vertices of $G$, or show that no such function exists.

Context

Using the graphs $G_d(N)$ from [10], the authors show that for arbitrarily large $q = \mathrm{HG}(G)$ the hat guessing number of $G'$ can exceed $q^2$ (specifically reaching $q^2+q$), so adding a universal vertex can dramatically increase the hat guessing number.

Source paper

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