Summary: \textit{S. Riis} [Electron. J. Comb. 14, No. 1, R44, 17 p. (2007; Zbl 1122.05041)] introduced a guessing game for graphs which is equivalent to finding protocols for network coding. In this paper we prove upper and lower bounds for the winning probability of the guessing game on undirected graphs. We find optimal bounds for perfect graphs and minimally imperfect graphs, and present a conjecture relating the exact value for all graphs to the fractional chromatic number.
Recommendations
- The linear guessing number of undirected graphs
- Guessing numbers and extremal graph theory
- On the guessing number of shift graphs
- Hat guessing numbers of degenerate graphs
- Hat Guessing Numbers of Strongly Degenerate Graphs
- The number of matchings in random graphs
- On the matching number of an uncertain graph
- Ulam numbers of graphs
- The number of graphs and a random graph with a given degree sequence
- On the hat guessing number of a planar graph class
Cited in
(10)- On the guessing number of shift graphs
- Guessing numbers and extremal graph theory
- The linear guessing number of undirected graphs
- Guessing games on triangle-free graphs
- Finite dynamical systems, hat games, and coding theory
- The three colour hat guessing game on cycle graphs
- Guessing numbers of odd cycles
- Construction of storage codes of rate approaching one on triangle-free graphs
- On the influence of the interaction graph on a finite dynamical system
- Bounds on guessing numbers and secret sharing combining information theory methods.
This page was built for publication: The guessing number of undirected graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q640453)
