View PDF HTML (experimental)

Abstract:We initiate the study of the hat guessing number of a graph where the adversary is only allowed to provide a proper coloring of the graph. This is the largest number $q$ for which there is a guessing strategy on each vertex that only depends on its neighborhood, such that for every proper coloring of the graph with $q$ colors at least one vertex guesses its color correctly. In this variation, we prove that the hat guessing number of the complete graphs on $n$ vertices is $2n - 1$, which is roughly twice the classical hat guessing number of the complete graph. Our winning strategy is related to finding perfect matchings between the middle layers of the boolean poset of dimension $2n - 1$. We prove that the hat guessing number of all trees on $n \geq 3$ vertices is equal to $4$. We derive general upper bounds in terms of the number of vertices, chromatic number, and maximum degree, and obtain improved bounds for book graphs. Using our results and an ILP formulation of the problem, we determine the exact hat guessing number for all graphs on at most $4$ vertices, give bounds on graphs on $5$ vertices, and suggest some open problems.

Submission history

From: Sam Adriaensen [view email]
[v1] Thu, 5 Mar 2026 07:52:36 UTC (13 KB)
[v2] Mon, 8 Jun 2026 14:34:47 UTC (13 KB)
[v3] Thu, 23 Jul 2026 09:03:59 UTC (16 KB)