Guessing Games on Triangle-free Graphs
  The guessing game introduced by Riis is a variant of the "guessing your own hats" game and can be played on any simple directed graph G on n vertices. For each digraph G, it is proved that there exists a unique guessing number gn(G) associated to the guessing game played on G. When we consider the directed edge to be bidirected, in other words, the graph G is undirected, Christofides and Markstrom introduced a method to bound the value of the guessing number from below using the fractional clique number Kf(G). In particular they showed gn(G) >= |V(G)| - Kf(G). Moreover, it is pointed out that equality holds in this bound if the underlying undirected graph G falls into one of the following categories: perfect graphs, cycle graphs or their complement. In this paper, we show that there are triangle-free graphs that have guessing numbers which do not meet the fractional clique cover bound. In particular, the famous triangle-free Higman-Sims graph has guessing number at least 77 and at most 78, while the bound given by fractional clique cover is 50. 
Peter J. Cameron, Anh N. Dang, Soren Riis
math.CO cs.IT math.IT