加载中…
We show that every proper minor-closed class of graphs admits a -bit adjacency labelling scheme. Equivalently, for every proper minor-closed class and every positive integer there exists an -vertex graph such that every -vertex graph in is isomorphic to an induced subgraph of . 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).

生成讲解博客的中文版本

生成AI智能校验的中文版本