Name
Abstract | ||
|---|---|---|
We study the hat chromatic number of a graph defined in the following way: there is one player at each vertex of a graph G, an adversary places a hat of one of K colors on the head of each player, two players can see each other's hats if and only if they are at adjacent vertices. All players simultaneously try to guess the color of their hat. The players cannot communicate but collectively determine a strategy before the hats are placed. The hat chromatic number, denoted by HG(G), is the largest number K of colors such that the players are able to fix a strategy that will ensure that for every possible placement of hats at least one of the players guesses correctly. We determine HG(G) for several classes of graphs, for others we establish some bounds. We investigate connections between the hat chromatic number, the chromatic number and the coloring number. We also introduce several variants of the game: with multiple guesses, restrictions on allowed strategies or restrictions on colorings. We show examples how the modified games can be used to obtain interesting results for the original game. (C) 2021 Elsevier B.V. All rights reserved. |
Year | DOI | Venue |
|---|---|---|
2021 | 10.1016/j.disc.2021.112620 | DISCRETE MATHEMATICS |
Keywords | DocType | Volume |
Graph coloring, Hat chromatic number | Journal | 344 |
Issue | ISSN | Citations |
12 | 0012-365X | 0 |
PageRank | References | Authors |
0.34 | 0 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Bartlomiej Bosek | 1 | 66 | 14.26 |
| Andrzej Dudek | 2 | 114 | 23.10 |
| Michał Farnik | 3 | 0 | 0.34 |
| Jarosław Grytczuk | 4 | 168 | 18.83 |
| Przemysław Mazur | 5 | 0 | 0.34 |