ADJACENCY LABELLING FOR PROPER MINOR-CLOSED GRAPH CLASSES
Vida Dujmović Cyril Gavoille Gwenaël Joret Piotr Micek Pat Morin David R. Wood · 2026
Read ADJACENCY LABELLING FOR PROPER MINOR-CLOSED GRAPH CLASSES by Vida Dujmović Cyril Gavoille Gwenaël Joret Piotr Micek Pat Morin David R. Wood (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-06616.txt.
Introduction
Vida Dujmović and five co-authors prove that graphs avoiding a fixed minor can be labeled so adjacency is readable from short labels alone. An adjacency labeling scheme assigns each vertex a small binary label such that two labels reveal whether an edge joins them. For every proper minor-closed class, they achieve labels only slightly longer than the logarithm of the vertex count.
Equivalently, one universal graph with barely more than n vertices contains every n-vertex graph of the class as an induced subgraph. Both results are optimal apart from lower-order terms. They extend earlier theorems for planar graphs to all proper minor-closed classes, answering an open question raised in that earlier work.
Catalog record
| CREATOR | Vida Dujmović Cyril Gavoille Gwenaël Joret Piotr Micek Pat Morin David R. Wood |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 142 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.06616
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
ADJACENCY LABELLING FOR PROPER MINOR-CLOSED GRAPH CLASSES Vida Dujmović Cyril Gavoille Gwenaël Joret Piotr Micek Pat Morin David R. Wood Abstract We show that every proper minor-closed class of graphs admits a ( 1 + o ( 1 ) ) log 2 n (1+o(1))\log_{2}n -bit adjacency labelling scheme. Equivalently, for every proper minor-closed class 𝒢 \mathcal{G} and every positive integer n n there exists an n 1 + o ( 1 ) n^{1+o(1)} -vertex graph U U such that every n n -vertex graph in 𝒢 \mathcal{G} is isomorphic to an induced subgraph of U U . Both results are optimal up to the lower order term. 1 Introduction Let \mathcal{G} be a class of graphs and let f:\mathbb{N}\to\mathbb{N} be a function. We say that \mathcal{G} admits an f(n) -bit adjacency labelling scheme if there exists a function A:(\{0,1\}^{*})^{2}\to\{0,1\} such that for all positive integers n , for every n -vertex graph G\in\mathcal{G} , there exists a function \ell:V(G)\to\{0,1\}^{*} such that |\ell(v)|\leqslant f(n) for each vertex v in G , and such that for every two vertices u , v in G , A(\ell(u),\ell(v))=\begin{cases}0&\textrm{if $uv\notin E(G)$},\\ 1&\textrm{if $uv\in E(G)$}.\end{cases} In this paper we prove the following result. (All logarithms are in base 2 .) Theorem 1 . Every proper minor-closed class of graphs admits a (1+o(1))\log n -bit adjacency labelling scheme. Note that all the dependence on the fixed proper minor-closed class in 1 is in the o(\log n) term. Also, 1 is optimal up to the o(\log n) term, which is \mathcal{O}\left((\log n)^{3/4}\right) . The proof of 1 is constructive. For every fixed proper minor-closed class \mathcal{G} , there is a polynomial-time algorithm that takes a graph G\in\mathcal{G} as input and constructs the labelling \ell:V(G)\to\{0,1\}^{*} . A consequence 1 1 1 In fact, the viewpoints of adjacency labelling schemes and induced-universal graphs are essentially equivalent. A minor detail is that the labelling schemes need to be injective for the equivalence to hold but this is the case for those developed in this paper. See [ 26 , Section 2.1] for more details on the connection between the two notions. of 1 is the existence of induced-universal graphs with a near-linear number of vertices for n -vertex graphs belonging to a fixed proper minor-closed class of graphs. Corollary 2 . For every proper minor-closed class \mathcal{G} , for every positive integer n , there exists a graph U with n^{1+o(1)} vertices such that every n -vertex graph in \mathcal{G} is isomorphic to an induced subgraph of U . 1.1 State of the Art Adjacency labeling schemes were introduced in the late 1980s by 18 and independently in the PhD thesis of 24 . Since this initial work, adjacency labelling schemes and, more generally, informative labelling schemes have remained a very active area of research. Here we review results most relevant to the current work, namely results on trees, bounded treewidth graphs, and planar graphs. We start with a simple example to better grasp the notion of labelling schemes. Given an n -vertex tree T , fix an arbitrary vertex to be the root of T , and assign each vertex of T with an identifier, i.e. a number in \{0,\ldots,n-1\} . For each non-root vertex v of T , let the label of v be the pair consisting of its identifier and the identifier of its parent. For the root vertex of T , let its label be the pair consisting of two copies of its identifier. Clearly, given two labels of vertices in T , a test of adjacency is simply to verify whether an identifier of one vertex is equal to a stored identifier of the parent of the other vertex. This constitutes a \lceil\log(n^{2})\rceil=\lceil 2\log n\rceil -bit adjacency labelling scheme for trees. There is a fascinating series of results improving on this simple scheme for trees. In 1990, Chung [ 4 ] gave an adjacency labelling scheme for n -vertex trees with each label of length \log n+\mathcal{O}(\log\log n) . 2 devised a scheme with labels of length \log n+\mathcal{O}(\log^{*}n) . Finally, in 2015, 1 gave a (\log n+\mathcal{O}(1)) -bit adjacency labelling scheme for trees, which is optimal up to the \mathcal{O}(1) term. Indeed, consider an n -vertex graph with no two vertices having the same neighborhood (e.g. a path for n\geqslant 4 ). In any adjacency labelling scheme, each vertex must be assigned a distinct label and therefore one label must be of length at least \lceil\log n\rceil . In 2007, 12 presented a (1+o(1))\log n -bit adjacency labelling scheme for graphs of bounded treewidth. This is particularly relevant to the topic of this paper because of the following famous application of the graph minor structure theorem: 6 showed that every graph in a proper minor-closed class can be edge 2 -coloured so that each monochromatic subgraph has bounded treewidth. Therefore, given a proper minor-closed class of graphs \mathcal{G} , for each G in \mathcal{G} , fix such a 2 -coloring of the edges of G , say with red and blue, and label each vertex of G by the concatenation of the two labels given by the adjacency labelling schemes for the red subgraph of G and for the blue subgraph of G . Thus, all labels are of length (2+o(1))\log n . Given two labels, to test adjacency simply test whether there is a blue edge or whether there is a red edge. This gives a (2+o(1))\log n -bit adjacency labelling scheme for a fixed proper minor-closed class of graphs, which remained the best-known scheme up to the present work. Planar graphs are a prominent example of a proper minor-closed class of graphs and there is a long history of research on their adjacency labelling schemes. Since planar graphs are 5 -degenerate, they admit a simple \lceil 6\log n\rceil -bit adjacency labelling scheme, which was already observed by 24 . 18 use a similar approach that makes use of the fact that planar graphs have arboricity 3 (so their edges can be partitioned into three forests [ 25 ] ) to devise an adjacency labelling scheme for planar graphs whose labels have length at most \lceil 4\log n\rceil . Of course, the later result of 12 also applies and gives a scheme with labels of length (2+o(1))\log n . The most recent breakthrough came with the application of the product structure theorem for planar graphs by 9 . In 2020, 3 recognized that the product structure is particularly useful for adjacency labelling, breaking the (2+o(1))\log n barrier by introducing a scheme with labels of length (\frac{4}{3}+o(1))\log n . Finally, in 2020 8 used the product structure theorem to give a (1+o(1))\log n -bit adjacency labelling scheme for planar graphs, which is optimal up to the lower order term. In [ 8 ] , the lower order term is \mathcal{O}(\sqrt{\log n\log\log n}) . 13 later introduced a simplification that reduces the lower order term to \mathcal{O}(\sqrt{\log n}) and allows for the adjacency testing function to be implemented in constant time in a realistic model of computation. The adjacency labelling scheme of 8 works for graphs embeddable in any fixed surface, and generally for any minor-closed class excluding a fixed apex graph