Hat Guessing on Books and Windmills

2020/10/25 by Xiaoyu He, He, Xiaoyu, Yuzu Ido +3 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2010.13249

openalex publication_date 2020/10/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The hat-guessing number is a graph invariant defined by Butler, Hajiaghayi, Kleinberg, and Leighton. We determine the hat-guessing number exactly for book graphs with sufficiently many pages, improving previously known lower bounds of He and Li and exactly matching an upper bound of Gadouleau. We prove that the hat-guessing number of K_3,3 is 3, making this the first complete bipartite graph K_n,n for which the hat-guessing number is known to be smaller than the upper bound of n+1 of Gadouleau and Georgiou. Finally, we determine the hat-guessing number of windmill graphs for most choices of parameters.

Citations

• On Representatives of Subsets

Cited by

• Proper Hat-Guessing on Two-Spine Book Graphs

Related

• Hat guessing number and guaranteed subgraphs
• The hat guessing number of graphs
• Hat guessing number of planar graphs is at least 22
• On the hat guessing number of a planar graph class
• On the Hat Guessing Number of Graphs