Hat guessing with proper colorings

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\ge 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.

12 pages. UPDATE: We added Theorem 1.3, which gives bounds the proper coloring hat guessing number by a multiple of the maximum degree. Extra Update: we updated the Acknowledgements