Guessing games on triangle-free graphs

Peter J. Cameron ; Anh N. Dang¹ ; Søren Riis

¹Queen Mary University

The electronic journal of combinatorics, Tome 23 (2016) no. 1

Résumé

The guessing game introduced by Riis [Electron. J. Combin. 2007] 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, Christofides and Markström [Electron. J. Combin. 2011] 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) \geq |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$.

Détail

DOI : 10.37236/4731

Classification : 05C57, 91A43
Mots-clés : guessing game, fractional clique cover, triangle-free graphs