OPTIMAL ADJACENCY LABELS FOR SUBGRAPHS OF CARTESIAN PRODUCTS

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 induced-universal graphs) meeting the information-theoretic minimum, then so do the classes of subgraphs and induced subgraphs of Cartesian products of graphs in F. Our proof uses ideas from randomized communication complexity, hashing, and additive combinatorics and improves upon recent results of Chepoi, Labourel, and Ratel