Hat guessing numbers of degenerate graphs (Q2200434)

Summary: Recently, \textit{M. Farnik} [A hat guessing game. Kraków: Jagiellonian University (PhD Thesis) (2015)] asked whether the hat guessing number \(\text{HG}(G)\) of a graph \(G\) could be bounded as a function of its degeneracy \(d\), and \textit{B. Bosek} et al. [``Hat chromatic number of graphs'', Preprint, \url{arXiv:1905.04108}] showed that \(\text{HG}(G)\ge 2^d\) is possible. We show that for all \(d\ge 1\) there exists a \(d\)-degenerate graph \(G\) for which \(\text{HG}(G) \ge 2^{2^{d-1}} \). We also give a new general method for obtaining upper bounds on \(\text{HG}(G)\). The question of whether \(\text{HG}(G)\) is bounded as a function of \(d\) remains open.