Hat problem on bicyclic graphs

Abstract

In the hat problem, each of n players is randomly fitted with a blue or red hat. Everybody can try to guess simultaneously his own hat color by looking at the hat colors of the other players. The team wins if at least one player guesses his hat color correctly, and no one guesses his hat color wrong; otherwise the team loses. The aim is to maximize the probability of winning. Note that every player can see everybody excluding himself. This problem has been considered on a graph, where the vertices correspond to the players, and a player can see each player to whom he is connected by an edge. The solution of the hat problem on graphs is known for several classes of graphs including bipartite graphs, cycles and unicyclic graphs. We investigate the problem on bicyclic graphs. © 2018 Utilitas Mathematica Publishing Inc. All rights reserved.