Key points are not available for this paper at this time.
For any hereditary graph class F , we construct optimal adjacency labeling schemes for the classes of subgraphs and induced subgraphs of Cartesian products of graphs in F .As a consequence, we show that, if F admits efficient adjacency labels (or, equivalently, small induceduniversal graphs) meeting the information-theoretic minimum, then the classes of subgraphs and induced subgraphs of Cartesian products of graphs in F do too.Our proof uses ideas from randomized communication complexity, hashing, and additive combinatorics, and improves upon recent results of Chepoi, Labourel, and Ratel Journal of Graph Theory, 2020.
Esperet et al. (Mon,) studied this question.