Hat guessing number of planar graphs is at least 22

2023/01/24 by Aleksei Latyshev, Latyshev, Aleksei, K. P. Kokhas +1 · 1 citation
Computer Science · #05C57 #Advanced Graph Theory Research #Artificial Intelligence in Games #Combinatorics (math.CO) #F.2.2 #FOS: Mathematics #G.2.2

paper · pdf · doi:10.48550/arxiv.2301.10305

openalex publication_date 2023/01/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We analyze the version of the deterministic Hats game. In this paper, we present new constructors, i.e. theorems that allow built winning strategies for the sages on different graphs. Using this technique we calculate the hat guessing number HG_s(G) for paths and "petunias", and present a planar graph G for which HG₁(G) ≥ 22.

Cited by

• Graph Sensitivity under Join and Decomposition

Related

• On the Hat Guessing Number of Graphs
• The Hats game. The power of constructors
• The hat guessing number of graphs
• On the hat guessing number of a planar graph class
• Hat guessing numbers of strongly degenerate graphs