Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: 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.

14
The categories of this paper are: math-ph
35
The categories of this paper are: mtrl-th
33
The categories of this paper are: plasm-ph
7
The categories of this paper are: hep-th
32
The categories of this paper are: atom-ph
26
The categories of this paper are: bayes-an
0
The categories of this paper are: hep-ph
19
The categories of this paper are: eess
18
The categories of this paper are: econ
13
The categories of this paper are: quant-ph
16
The categories of this paper are: stat
6
The categories of this paper are: astro-ph
9
The categories of this paper are: nlin
25
The categories of this paper are: patt-sol
20
The categories of this paper are: acc-phys
23
The categories of this paper are: solv-int