Hat guessing number and guaranteed subgraphs

arXiv2109.13422MaRDI QIDQ6504690FDOQ6504690

Authors: Peter Bradshaw 

Abstract: The hat guessing number of a graph is a parameter related to the hat guessing game for graphs introduced by Winkler. In this paper, we show that graphs of sufficiently large hat guessing number must contain arbitrary trees and arbitrarily long cycles as subgraphs. More precisely, for each tree $T$, there exists a value $N=N(T)$ such that every graph that does not contain $T$ as a subgraph has hat guessing number at most $N$, and for each integer $cgeq3$, there exists a value $N^{\prime }=N^{\prime }(c)$ such that every graph with no cycle of length greater than $c$ has hat guessing number at most $N^{\prime }$.

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Games on graphs (graph-theoretic aspects) (05C57)

This page was built for publication: Hat guessing number and guaranteed subgraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6504690)