An upper bound on the proper hat guessing number of graphs

@misc{kakatelis2026upper,
  title = {{An upper bound on the proper hat guessing number of graphs}},
  author = {Ioannis Kakatelis},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.04124},
  eprint = {2610.04124},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.04124},
  note = {CC BY 4.0},
}

TY  - UNPB
TI  - An upper bound on the proper hat guessing number of graphs
AU  - Ioannis Kakatelis
PY  - 2026
DA  - 2026/10/06
PB  - arXiv
DO  - 10.48550/arxiv.2610.04124
UR  - https://arxiv.org/abs/2610.04124
AB  - We study the proper hat guessing game on graphs, introduced by Adriaensen et al. in Hat guessing with proper colorings. 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 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 Δ≥ 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 ≈ 1.366. Finally, we prove that graphs of maximum degree (1−γ)n for some fixed γ∈ (0,1] cannot have HG_P(G) = (2−o(1))n.
ER  -