Esperet, L, Harms, N and Zamaraev, V ORCID: 0000-0001-5755-4141
(2023)
Optimal Adjacency Labels for Subgraphs of Cartesian Products.
.
Abstract
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 the classes of subgraphs and induced subgraphs of Cartesian products of graphs in F do too. Our proof uses ideas from randomized communication complexity and hashing, and improves upon recent results of Chepoi, Labourel, and Ratel [Journal of Graph Theory, 2020].
Item Type: | Conference or Workshop Item (Unspecified) |
---|---|
Divisions: | Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science |
Depositing User: | Symplectic Admin |
Date Deposited: | 24 Aug 2023 09:40 |
Last Modified: | 24 Aug 2023 09:41 |
DOI: | 10.4230/LIPIcs.ICALP.2023.57 |
Open Access URL: | https://drops.dagstuhl.de/opus/volltexte/2023/1810... |
URI: | https://livrepository.liverpool.ac.uk/id/eprint/3172329 |