论文标题
帽子猜测数量的退化图
Hat Guessing Numbers of Degenerate Graphs
论文作者
论文摘要
最近，法尼克（Farnik）问，图$ g $的帽子猜测数字$ \ text {hg}（g）$是否可以作为其退化$ d $的函数以及Bosek，Dudek，Farnik，Grytczuk和Mazur的函数，显示了$ \ \ \ text {hg}（g ge）\ ge 2^d $。我们证明，对于所有$ d \ ge 1 $，存在$ d $ -degenate图$ g $，$ \ text {hg}（g）（g）\ ge 2^{2^{2^{d-1}} $。我们还提供了一种新的通用方法，用于在$ \ text {hg}（g）$上获得上限。 $ \ text {hg}（g）$作为$ d $的函数是否有限的问题保持开放。
Recently, Farnik asked whether the hat guessing number $\text{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 $\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.
