Abstract
For a given number of colours, s, the guessing number of a graph is the base s
logarithm of the size of the largest family of colourings of the vertex
set of the graph such that the colour of each vertex can be determined
from the colours of the vertices in its neighbourhood. An upper bound
for the guessing number of the n-vertex cycle graph Cn is n/2. It is known that the guessing number equals n/2 whenever n is even or s is a perfect square. We show that, for any given integer s≥2, if a is the largest factor of s less than or equal to s√, for sufficiently large odd n, the guessing number of Cn with s colours is (n−1)/2+logs(a).
This answers a question posed by Christofides and Markström in 2011.We
also present an explicit protocol which achieves this bound for every n. Linking this to index coding with side information, we deduce that the information defect of Cn with s colours is (n+1)/2−logs(a) for sufficiently large odd n.
| Original language | English |
|---|---|
| Article number | #P1.45 |
| Number of pages | 20 |
| Journal | Electronic Journal of Combinatorics |
| Volume | 24 |
| Issue number | 1 |
| Early online date | 3 Mar 2017 |
| Publication status | Published - Mar 2017 |
Keywords
- guessing number
- graph theory
- cycle
- entropy
- broadcasting with side information
- combinatorics
- information theory
- cycle graph
- information defect
- index codes
- unicast