An upper bound on the proper hat guessing number of graphs

Source abstract

We study the proper hat guessing game on graphs, introduced by Adriaensen et al. \cite{adriaensen2026hatguessingpropercolorings}. In this game, the players are seated on the vertices of a graph $G$ and assigned hats from a set of $k$ colors such that the resulting assignment forms a proper coloring. The visibility of each vertex is limited to the hat colors of their neighborhood. Then they must simultaneously output a guess about the color of their own hat. The players win if at least one guess is correct. A parameter related to this problem is the proper hat guessing number $\operatorname{HG}_{P}(G)$ that is the maximum number of colors $m$ such that the players can guarantee a winning strategy. Motivated by the work of Shurman et al. \cite{shurman2026upper}, we establish the first upper bound that depends both on the number of vertices $n$ and the maximum degree $Δ$ in the case where $Δ\geq \frac{n}{e+1}$. This result leads us to show that the proper hat guessing number of the binomial random graph $G_{n,1/2}$ is bounded above by $cn$, where $c \approx 1.366$. Finally, we prove that graphs of maximum degree $(1-γ)n$ for some fixed $γ\in (0,1]$ cannot have $\operatorname{HG}_{P}(G) = (2-o(1))n$.