Guessing games on triangle-free graphs (Q278884)

Summary: The guessing game introduced by \textit{S. Riis} [Electron. J. Comb. 14, No. 1, Research paper R44, 17 p. (2007; Zbl 1122.05041)] 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 \(\mathrm{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, \textit{D. Christofides} and \textit{K. Markström} [ibid. 18, No. 1, Research Paper P192, 19 p. (2011; Zbl 1337.05077)] introduced a method to bound the value of the guessing number from below using the fractional clique cover number \(\kappa_f(G)\). In particular they showed \(\mathrm{gn}(G) \geqslant |V(G)| - \kappa_f(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.