
arXiv: 2009.04529
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.
Extremal problems in graph theory, Combinatorial probability, Measures of information, entropy, graph entropy, G.2.1, G.2.1; G.2.2; G.2.3; H.1.1, network coding, G.2.2, G.2.3, circuit complexity, Coloring of graphs and hypergraphs, 05C57, 05C35, 05C15, 94A15, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), H.1.1
Extremal problems in graph theory, Combinatorial probability, Measures of information, entropy, graph entropy, G.2.1, G.2.1; G.2.2; G.2.3; H.1.1, network coding, G.2.2, G.2.3, circuit complexity, Coloring of graphs and hypergraphs, 05C57, 05C35, 05C15, 94A15, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), H.1.1
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
