Geodesic
Cliques and constructors in ``Hats'' game.~I
Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part XI, Tome 488 (2019), pp. 66-96

Voir la notice de l'article provenant de la source Math-Net.Ru

We analyze the following general variant of deterministic “Hats” game. Several sages wearing colored hats occupy the vertices of a graph, $k$-th sage can have hats of one of $h(k)$ colors. Each sage tries to guess the color of his own hat merely on the basis of observing the hats of his neighbours without exchanging any information. A predetermined guessing strategy is winning if it guarantees at least one correct individual guess for every assignment of colors. For complete graphs and for cycles we solve the problem of describing fuctions $h(k)$ for which the sages win. We develop “theory of construcors”, that is a collection of theorems demonstrating how one can construct new graphs for which the sages win. We define also new game “Check by rook” which is equivalent to Hats game on $4$-cycle and give complete analysis of this game. 
@article{ZNSL_2019_488_a3,
     author = {K. P. Kokhas and A. S. Latyshev},
     title = {Cliques and constructors in {``Hats''} {game.~I}},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {66--96},
     publisher = {mathdoc},
     volume = {488},
     year = {2019},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_2019_488_a3/}
}
TY  - JOUR
AU  - K. P. Kokhas
AU  - A. S. Latyshev
TI  - Cliques and constructors in ``Hats'' game.~I
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 2019
SP  - 66
EP  - 96
VL  - 488
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/ZNSL_2019_488_a3/
LA  - ru
ID  - ZNSL_2019_488_a3
ER  - 
%0 Journal Article
%A K. P. Kokhas
%A A. S. Latyshev
%T Cliques and constructors in ``Hats'' game.~I
%J Zapiski Nauchnykh Seminarov POMI
%D 2019
%P 66-96
%V 488
%I mathdoc
%U http://geodesic.mathdoc.fr/item/ZNSL_2019_488_a3/
%G ru
%F ZNSL_2019_488_a3
K. P. Kokhas; A. S. Latyshev. Cliques and constructors in ``Hats'' game.~I. Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part XI, Tome 488 (2019), pp. 66-96. http://geodesic.mathdoc.fr/item/ZNSL_2019_488_a3/