Adjacency labelling for proper minor-closed graph classes

Vida DujmoviÄ; Cyril Gavoille; GwenaÃ«l Joret; Piotr Micek; Pat Morin; David R. Wood

graph theory

Adjacency labelling for proper minor-closed graph classes

arXiv:2605.06616

summary

The paper proves that every proper minor‑closed class of graphs admits an adjacency labeling scheme using (1+o(1))·log₂ n bits, equivalently showing the existence of an n^{1+o(1)}‑vertex universal graph for such classes.

Abstract

We show that every proper minor-closed class of graphs admits a $(1 + o (1)) lo g_{2} n$ -bit adjacency labelling scheme. Equivalently, for every proper minor-closed class $G$ and every positive integer $n$ there exists an $n^{1 + o (1)}$ -vertex graph $U$ such that every $n$ -vertex graph in $G$ is isomorphic to an induced subgraph of $U$ . Both results are optimal up to the lower order term. They generalize the corresponding results for planar graphs and apex-minor-free classes (DujmoviÄ et al., J.~ACM 2021) to all proper minor-closed classes, answering the open question raised in that paper and anticipated earlier by Bonamy, Gavoille, and Pilipczuk (SODA 2020).

Improved writing throughout. Fixed bug related to injectivity of clique labels

Topics & keywords

#adjacency labeling #minor-closed graph classes #universal graphs #planar graphs #graph encodingadjacency labeling schemeproper minor-closed classlogarithmic label sizeinduced subgraph universal graphinjectivity of clique labels