We analyze the following version of the deterministic HATS game. We have a graph G, and a sage resides at each vertex of G. When the game starts, an adversary puts on the head of each sage a hat of a color arbitrarily chosen from a set of k possible colors. Each sage can see the hat colors of his neighbors but not his own hat color. All of sages are asked to guess their own hat colors simultaneously, according to a predetermined guessing strategy and the hat colors they see, where no communication between them is allowed. The strategy is winning if it guarantees at least one correct individual guess for every assignment of colors. Given a graph G, its hat guessing number HG(G) is the maximal number k such that there exists a winning strategy. We disprove the hypothesis that HG(G)≤Δ+1 and demonstrate that diameter of graph and HG(G) are independent.

Original languageEnglish
Article number112868
JournalDiscrete Mathematics
Volume345
Issue number7
DOIs
StatePublished - 1 Jul 2022

    Research areas

  • Deterministic strategy, Graphs, Hat guessing game, Hat guessing number

    Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Theoretical Computer Science

ID: 98395538