Esperet, Louis, Harms, Nathaniel and Zamaraev, Viktor 
ORCID: 0000-0001-5755-4141
(2022)
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, hashing, and additive combinatorics, and improves upon recent results of Chepoi, Labourel, and Ratel [Journal of Graph Theory, 2020].
| Item Type: | Conference or Workshop Item (Unspecified) |
|---|---|
| Additional Information: | 13 pages, revised version |
| Uncontrolled Keywords: | cs.DS, cs.DS, math.CO, 05C78, 05C76, 68R10 |
| Divisions: | Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 13 Jul 2023 15:28 |
| Last Modified: | 01 May 2024 06:25 |
| Open Access URL: | https://doi.org/10.4230/LIPIcs.ICALP.2023.57 |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3171679 |
Share
Share
