Optimal Adjacency Labels for Subgraphs of Cartesian Products

Esperet, L, Harms, N and Zamaraev, V ORCID: 0000-0001-5755-4141 (2023) Optimal Adjacency Labels for Subgraphs of Cartesian Products. .

Access the full-text of this item by clicking on the Open Access link.

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