Adjacency labelling for proper minor-closed graph classes

2026/05/07 by Vida Dujmović, Cyril Gavoille, Gwenaël Joret +3 · 1 voice
Computer Science · Mathematics · #cs.DM #math.CO

paper · pdf · doi:10.48550/arxiv.2605.06616

arxiv published 2026/05/07 · arxiv updated 2026/07/13

Abstract

We show that every proper minor-closed class of graphs admits a (1+o(1))log₂ 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).

Citations

• The price of homogeneity is polynomial
• Structure of k-Matching-Planar Graphs
• Polynomial Bounds for the Graph Minor Structure Theorem
• Tight bounds on adjacency labels for monotone graph classes
• Implicit representation of sparse hereditary families
• The Implicit Graph Conjecture is False
• Optimal labelling schemes for adjacency, comparability, and reachability
• Quickly excluding a non-planar graph
• Shorter Labeling Schemes for Planar Graphs
• Graph product structure for non-minor-closed classes
• Planar graphs have bounded queue-number
• Optimal induced universal graphs and adjacency labeling for trees
• Planar Reachability in Linear Space and Constant Time
• List-coloring apex-minor-free graphs
• A New Proof of the Flat Wall Theorem
• Algorithmic Graph Minor Theory: Decomposition, Approximation, and Coloring
• A Characterization of Comparability Graphs and of Interval Graphs
• Edge-Disjoint Spanning Trees of Finite Graphs

Discussions

• Vida Dujmovi\'c, Gwena\"el Joret, Cyril Gavoille, Piotr Micek, Pat Morin, David R. Wood: Adjacency labelling for proper minor-closed graph classes https://arxiv.org/abs/2605.06616 https://arxiv.org/pd [bsky, 0 points, 0 comments]

Related

• Small But Unwieldy: A Lower Bound on Adjacency Labels for Small Classes
• Adjacency labeling schemes and induced-universal graphs
• Labeling Schemes for Bounded Degree Graphs
• Adjacency Labeling Schemes for Small Classes
• Optimal labelling schemes for adjacency, comparability, and reachability