Guessing numbers and extremal graph theory (Q2152800)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Guessing numbers and extremal graph theory |
scientific article |
Statements
Guessing numbers and extremal graph theory (English)
0 references
11 July 2022
0 references
Summary: 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 \(\leqslant 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.
0 references
network coding
0 references
circuit complexity
0 references
graph entropy
0 references
0 references