Adjacency labelling for proper minor-closed graph classes

Vida Dujmović, Cyril Gavoille, Gwenaël Joret +3

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}$ a…