{"id":"arxiv/2605.06616","url":"https://arxiv.org/abs/2605.06616","tags":["cs.DM","math.CO"],"score":0,"title":"Adjacency labelling for proper minor-closed graph classes","domain":"cs.DM","source":"arxiv","authors":["Vida Dujmović","Cyril Gavoille","Gwenaël Joret","Piotr Micek","Pat Morin","David R. Wood"],"reviews":0,"subject":"cs.DM","summary":"We show that every proper minor-closed class of graphs admits a $(1+o(1))\\log_2 n$-bit adjacency labelling scheme. Equivalently, for every proper minor-closed class $\\mathcal{G}$ and every positive integer $n$ there exists an $n^{1+o(1)}$-vertex graph $U$ such that every $n$-vertex graph in $\\mathcal{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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-05-07","reactions":{}}