Recently, Farnik asked whether the hat guessing number $\mathrm{HG}(G)$ of a graph $G$ could be bounded as a function of its degeneracy $d$, and Bosek, Dudek, Farnik, Grytczuk and Mazur showed that $\mathrm{HG}(G)\ge 2^d$ is possible. We show that for all $d\ge 1$ there exists a $d$-degenerate graph $G$ for which $\mathrm{HG}(G) \ge 2^{2^{d-1}}$. We also give a new general method for obtaining upper bounds on $\mathrm{HG}(G)$. The question of whether $\mathrm{HG}(G)$ is bounded as a function of $d$ remains open.
@article{10_37236_9449,
author = {Xiaoyu He and Ray Li},
title = {Hat guessing numbers of degenerate graphs},
journal = {The electronic journal of combinatorics},
year = {2020},
volume = {27},
number = {3},
doi = {10.37236/9449},
zbl = {1448.05143},
url = {http://geodesic.mathdoc.fr/articles/10.37236/9449/}
}
TY - JOUR
AU - Xiaoyu He
AU - Ray Li
TI - Hat guessing numbers of degenerate graphs
JO - The electronic journal of combinatorics
PY - 2020
VL - 27
IS - 3
UR - http://geodesic.mathdoc.fr/articles/10.37236/9449/
DO - 10.37236/9449
ID - 10_37236_9449
ER -
%0 Journal Article
%A Xiaoyu He
%A Ray Li
%T Hat guessing numbers of degenerate graphs
%J The electronic journal of combinatorics
%D 2020
%V 27
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/9449/
%R 10.37236/9449
%F 10_37236_9449
Xiaoyu He; Ray Li. Hat guessing numbers of degenerate graphs. The electronic journal of combinatorics, Tome 27 (2020) no. 3. doi: 10.37236/9449
