1 Introduction
1.1 Communication-to-Graph Correspondence
1.2 Examples
1.3 Results
2 Preliminaries
2.1 Notation and Terminology
2.2 Communication Complexity
2.3 Boosting & Derandomization
2.4 Equality-Based Labeling Schemes
2.5 Basic Adjacency Sketches
3 Graph Theory & Contextual Results
3.1 The Speed of Hereditary Graph Classes
3.2 Constant-Size Deterministic Labeling Schemes
3.3 Minimal Factorial Families
3.4 The Bell Numbers Threshold
4 Bipartite Graphs
4.1 Equivalence to Bipartite Graphs
4.2 Decomposition Scheme for Bipartite Graphs
4.3 Monogenic Bipartite Graph Families
5 Interval & Permutation Graphs
5.1 Interval Graphs
5.2 Permutation Graphs
6 Graph Products
6.1 Other Graph Products
7 Equality-Based Communication Protocols and Labeling Schemes
7.1 Characterization as Equivalence-Interpretable
7.2 Cartesian Products Do Not Admit an Equality-Based Labeling Scheme
8 Twin-width
8.1 Preliminaries
8.2 From General Graphs to Bipartite Graphs
8.3 Bipartite Graphs of Bounded Twin-width
8.4 First-Order Labeling Schemes & Distance Sketching
A Proofs from Section 3
A.1 Tools
A.2 Classes Below the Bell Number
A.3 Minimal Classes Above the Bell Number
B Proofs from Section 6
B.1 Strong Products
B.2 Direct Product
B.3 Lexicographic Product
C Bibliographic Remark on Greater-Than