For a given number of colors, $s$, the guessing number of a graph is the (base $s$) logarithm of the cardinality of the largest family of colorings of the vertex set of the graph such that the color of each vertex can be determined from the colors of the vertices in its neighborhood. This quantity is related to problems in network coding, circuit complexity and graph entropy. We study the guessing number of graphs as a graph property in the context of classic extremal questions, and its relationship to the forbidden subgraph property. We find the extremal number with respect to the property of having guessing number $\leq a$, for fixed $a$. Furthermore, we find an upper bound on the saturation number for this property, and a method to construct further saturated graphs that lie between these two extremes. We show that, for a fixed number of colors, bounding the guessing number is equivalent to forbidding a finite set of subgraphs.
@article{10_37236_9851,
author = {Jo Martin and Puck Rombach},
title = {Guessing numbers and extremal graph theory},
journal = {The electronic journal of combinatorics},
year = {2022},
volume = {29},
number = {2},
doi = {10.37236/9851},
zbl = {1492.05074},
url = {http://geodesic.mathdoc.fr/articles/10.37236/9851/}
}
TY - JOUR
AU - Jo Martin
AU - Puck Rombach
TI - Guessing numbers and extremal graph theory
JO - The electronic journal of combinatorics
PY - 2022
VL - 29
IS - 2
UR - http://geodesic.mathdoc.fr/articles/10.37236/9851/
DO - 10.37236/9851
ID - 10_37236_9851
ER -
%0 Journal Article
%A Jo Martin
%A Puck Rombach
%T Guessing numbers and extremal graph theory
%J The electronic journal of combinatorics
%D 2022
%V 29
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/9851/
%R 10.37236/9851
%F 10_37236_9851
Jo Martin; Puck Rombach. Guessing numbers and extremal graph theory. The electronic journal of combinatorics, Tome 29 (2022) no. 2. doi: 10.37236/9851
