2021/02/14 by Aleksei Latyshev, Latyshev, Aleksei, K. P. Kokhas +1
Computer Science · Engineering · #Graph Labeling and Dimension Problems #graph theory and CDMA systems #Advanced Graph Theory Research
paper · pdf · doi:10.48550/arxiv.2102.07138
We analyze the following general version of the deterministic Hats game. Several sages wearing colored hats occupy the vertices of a graph. Each sage can have a hat of one of k colors. Each sage tries to guess the color of his own hat merely on the basis of observing the hats of his neighbors without exchanging any information. A predetermined guessing strategy is winning if it guarantees at least one correct individual guess for every assignment of colors. We present an example of a planar graph for which the sages win for k = 14. We also give an easy proof of the theorem about the Hats game on "windmill" graphs.