{"id":"arxiv/2603.04909","url":"https://arxiv.org/abs/2603.04909","tags":["math.CO"],"score":0,"title":"Hat guessing with proper colorings","domain":"math.CO","source":"arxiv","authors":["Sam Adriaensen","Peter Bentley","Anurag Bishnoi","Wouter Cames van Batenburg","Michael Kreiger","Lars van der Kuil","Saptarshi Mandal","Anurag Ramachandran","James Tuite"],"reviews":0,"subject":"math.CO","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-03-05","reactions":{}}