Hat Guessing Numbers of Strongly Degenerate Graphs
Charlotte Knierim, Anders Martinsson, Raphael Steiner · SIAM Journal on Discrete Mathematics · 2023
Abstract. Assume [Formula: see text] players are placed on [Formula: see text] vertices of a graph [Formula: see text]. The following game was introduced by Winkler: An adversary puts a hat on each player, where each hat has a color out of [Formula: see text] available colors. The players can see the hat of each of their neighbors in [Formula: see text] but cannot see their own hats. Using a predetermined guessing strategy, the players then simultaneously guess the color of their hats. The players win if at least one of them guesses correctly; otherwise, the adversary wins. The largest integer [Formula: see text] such that there is a winning strategy for the players is denoted by [Formula: see text], and this is called the hat guessing number of [Formula: see text]. Although this game has received much attention in recent years, not much is known about how the hat guessing number relates to other graph parameters. For instance, a natural open question is whether the hat guessing number can be bounded from above in terms of degeneracy. In this paper, we prove that the hat guessing number of a graph can be bounded from above in terms of a related notion, which we call strong degeneracy. We further give an exact characterization of graphs with bounded strong degeneracy. As a consequence, we significantly improve the best known upper bound on the hat guessing number of outerplanar graphs from [Formula: see text] to 40 and further derive upper bounds on the hat guessing number for any class of [Formula: see text]-free graphs with bounded expansion, such as the class of [Formula: see text]-free planar graphs; more generally, for [Formula: see text]-free graphs with bounded Hadwiger number or without a [Formula: see text]-subdivision; and for Erdős–Rényi random graphs with constant average degree.