Hat guessing with proper colorings

Sam Adriaensen, Peter Bentley, Anurag Bishnoi, Wouter Cames van Batenburg, Michael Kreiger, Lars van der Kuil, Saptarshi Mandal, Anurag Ramachandran, James Tuite

arXivarxiv/2603.04909Mar 5, 2026math.COscore 0

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…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2603.04909
curl -X POST /api/v1/records/arxiv/2603.04909/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2603.04909/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'