arxiv: 2605.06616 · v2 · submitted 2026-05-07 · 💻 cs.DM · math.CO

Recognition: 2 theorem links

· Lean Theorem

Adjacency labelling for proper minor-closed graph classes

Vida Dujmovi\'c , Gwena\"el Joret , Cyril Gavoille , Piotr Micek , Pat Morin , David R. Wood

Authors on Pith no claims yet

Pith reviewed 2026-05-11 01:47 UTC · model grok-4.3

classification 💻 cs.DM math.CO

keywords adjacency labellingminor-closed graph classesuniversal graphsinduced subgraphsplanar graphsgraph encodingsuccinct representations

0 comments

The pith

Every proper minor-closed class of graphs admits an adjacency labelling scheme with (1+o(1)) log n bits.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that any class of graphs excluding at least one fixed minor allows every n-vertex member to be assigned binary labels of length (1+o(1)) log n so that adjacency between any two vertices can be read off the pair of labels alone. This matters for a sympathetic reader because it supplies a compact encoding for adjacency queries in families such as planar graphs, bounded-genus graphs, and graphs of bounded treewidth, replacing the naive n-bit labels with labels that are nearly as short as the information-theoretic minimum. The same statement is rephrased as the existence, for each n, of a single host graph on n to the power 1 plus little-o vertices that contains every n-vertex graph from the class as an induced subgraph. Both forms of the result are shown to be tight up to the o(1) term in the exponent.

Core claim

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.

What carries the argument

An adjacency labelling scheme that assigns each vertex a binary string of length (1+o(1))log n such that two vertices are adjacent exactly when their labels satisfy a fixed predicate.

If this is right

Planar graphs, bounded-genus graphs, and graphs of bounded treewidth all admit (1+o(1))log n-bit adjacency labels.
Adjacency queries inside any such class can be answered from the pair of short labels alone.
The number of distinct n-vertex graphs in the class is at most the number of induced subgraphs of an n^{1+o(1)}-vertex graph.
The labelling size matches the known lower bound of log n for any graph class up to the lower-order additive term.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same universal-graph construction may yield compact representations for other sparse classes whose structure is governed by forbidden minors.
Efficient data structures for storing and querying large planar or minor-closed networks become feasible once the labels are available.
The result suggests that the extra power of o(log n) bits suffices to capture the global structure imposed by any single forbidden minor.

Load-bearing premise

The input graphs must belong to a class that excludes at least one fixed minor.

What would settle it

A concrete counter-example would be any proper minor-closed class in which some n-vertex graphs require adjacency labels of length omega(log n) for every n.

Figures

Figures reproduced from arXiv: 2605.06616 by Cyril Gavoille, David R. Wood, Gwena\"el Joret, Pat Morin, Piotr Micek, Vida Dujmovi\'c.

**Figure 1.** Figure 1: An arbitrary tree-decomposition (top) is refined into a new tree-decomposition view at source ↗

read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper shows every proper minor-closed graph class has an asymptotically optimal (1+o(1)) log n adjacency labeling scheme.

read the letter

The core advance is a uniform (1+o(1)) log₂ n bit adjacency labeling for any proper minor-closed class, plus the matching statement that every such class has an n^{1+o(1)}-vertex induced-universal graph. This covers planar graphs, bounded-treewidth graphs, and everything else that excludes a fixed minor, which is broader than the subclasses handled in earlier labeling results. The optimality claim up to lower-order terms is consistent with the obvious lower bounds from trees or grids inside these classes. The clean equivalence between the two formulations is also useful for anyone thinking about universal graphs in data structures. The argument presumably draws on the separator theorems and bounded-expansion properties that follow from excluding a minor, but the abstract alone does not reveal the exact steps or constants. Without the full proof I cannot check for hidden assumptions or whether the o(1) term is small enough to be practical. No circularity or internal contradiction appears in the stated claim. This is aimed at people working on labeling schemes, universal graphs, and algorithms for sparse hereditary classes. A reader who needs tight bounds for any minor-closed family will get direct value. The result is sharp and broad enough that it deserves a serious referee to check the details and see how the constants behave.

Referee Report

0 major / 3 minor

Summary. The manuscript proves that every proper minor-closed class of graphs admits an adjacency labelling scheme using (1+o(1)) log₂ n bits for its n-vertex members. Equivalently, for any such class G and positive integer n, there exists an induced-universal graph U on n^{1+o(1)} vertices that contains every n-vertex graph from G as an induced subgraph. Both statements are claimed to be optimal up to the lower-order term.

Significance. If the central proof is correct, the result is a substantial contribution to structural graph theory and adjacency labelling. It resolves the labelling complexity for the broad family of proper minor-closed classes (which includes planar graphs, bounded-genus graphs, and graphs of bounded treewidth) by achieving information-theoretically tight bounds up to o(1), matching known lower bounds from subclasses such as trees and grids. The clean equivalence between labelling schemes and induced-universal graphs is a useful framing, and the work leverages deep structural consequences of excluding a fixed minor (e.g., polynomial separators and bounded expansion) to obtain the construction.

minor comments (3)

[Section 1] The introduction would benefit from a short paragraph explicitly contrasting the new (1+o(1)) bound with the best previously known labelling lengths for specific minor-closed classes (e.g., planar graphs).
[Section 4] In the proof of the main theorem, the dependence of the o(1) term on the excluded minor is not quantified; adding a remark on how the hidden constants scale with the size of the forbidden minor would improve clarity.
[Section 6] A few sentences in the concluding remarks could be tightened to avoid repeating the abstract's optimality statement verbatim.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the manuscript, recognition of its significance for structural graph theory and adjacency labelling, and recommendation to accept.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The central result is a new theorem establishing (1+o(1))log₂n-bit adjacency labels (equivalently n^{1+o(1)}-vertex induced-universal graphs) for any proper minor-closed class. The proof relies on known structural consequences of excluding a fixed minor (bounded expansion, polynomial separators, etc.), which are external to this paper and not reduced to self-citation chains or fitted parameters. No equation or definition in the abstract or stated claim equates the output bound to an input by construction; the o(1) term is consistent with information-theoretic lower bounds for classes containing trees or grids. This is a standard non-circular theorem statement in structural graph theory.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The abstract invokes only the standard definition of proper minor-closed graph classes and the usual notions of adjacency labeling and induced subgraphs; no new entities, fitted constants, or ad-hoc axioms appear.

axioms (1)

standard math Standard axioms and definitions of graph theory, including the minor relation and the notion of a proper minor-closed class.
The result is stated directly in terms of these background definitions.

pith-pipeline@v0.9.0 · 5389 in / 1202 out tokens · 78680 ms · 2026-05-11T01:47:27.553941+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Theorem 1. Every proper minor-closed class of graphs admits a (1+o(1))log n-bit adjacency labelling scheme... via tree-decomposition in which every torso is in G_{k,a}
IndisputableMonolith/Foundation/AlexanderDuality.lean alexander_duality_circle_linking unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Lemma 13 (skinny tree-decompositions) and Lemma 14 (short tree-decompositions) controlling height and adhesion-width

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

27 extracted references · 27 canonical work pages

[1]

Optimal induced universal graphs and adjacency labeling for trees.J

Stephen Alstrup, Søren Dahlgaard, and Mathias Bæk Tejs Knudsen. Optimal induced universal graphs and adjacency labeling for trees.J. ACM, 64(4):27:1–27:22, 2017. doi:10.1145/3088513. Preliminary version appeared in FOCS 2015, pages 1311– 1326

work page doi:10.1145/3088513 2017
[2]

Improved labeling scheme for ancestor queries

Stephen Alstrup and Theis Rauhe. Improved labeling scheme for ancestor queries. 37 In David Eppstein, editor,Proc. 13th Annual ACM-SIAM Symposium on Discrete Algo- rithms(SODA ’02), pages 947–953. ACM/SIAM, 2002

work page 2002
[3]

Shorter labeling schemes for planar graphs.SIAM J

Marthe Bonamy, Cyril Gavoille, and Michał Pilipczuk. Shorter labeling schemes for planar graphs.SIAM J. Discrete Math., 36(3):2082–2099, 2022.doi:10.1137/ 20M1330464. Preliminary version appeared in SODA 2020, pages 446–462

work page 2082
[4]

Fan R. K. Chung. Universal graphs and induced-universal graphs.J. Graph Theory, 14(4):443–454, 1990.doi:10.1002/jgt.3190140408

work page doi:10.1002/jgt.3190140408 1990
[5]

Demaine, MohammadTaghi Hajiaghayi, and Ken ichi Kawarabayashi

Erik D. Demaine, MohammadTaghi Hajiaghayi, and Ken ichi Kawarabayashi. Algo- rithmic graph minor theory: Decomposition, approximation, and coloring. InProc. 46th Annual IEEE Symposium on Foundations of Computer Science(FOCS’05), pages 637–646. IEEE Computer Society, 2005.doi:10.1109/SFCS.2005.14

work page doi:10.1109/sfcs.2005.14 2005
[6]

Sanders, Bruce Reed, Paul Seymour, and Dirk Vertigan

Matt DeVos, Guoli Ding, Bogdan Oporowski, Daniel P . Sanders, Bruce Reed, Paul Seymour, and Dirk Vertigan. Excluding any graph as a minor allows a low tree- width 2-coloring.J. Combinatorial Theory, Series B, 91(1):25–41, 2004.doi:https: //doi.org/10.1016/j.jctb.2003.09.001

work page doi:10.1016/j.jctb.2003.09.001 2004
[7]

Diestel,Graph Theory, 5th edition, volume 173 ofGraduate Texts in Mathematics, Springer Berlin, Heidelberg, 2017,https://doi.org/10.1007/978-3-662-53622-3

Reinhard Diestel.Graph Theory, Fifth Edition, volume 173 ofGraduate texts in mathe- matics. Springer, 2017.doi:10.1007/978-3-662-53622-3

work page doi:10.1007/978-3-662-53622-3 2017
[8]

Adjacency labelling for planar graphs (and beyond).J

Vida Dujmović, Louis Esperet, Cyril Gavoille, Gwenaël Joret, Piotr Micek, and Pat Morin. Adjacency labelling for planar graphs (and beyond).J. ACM, 68(6):42:1– 42:33, 2021.doi:10.1145/3477542. Preliminary version appeared in FOCS 2020, pages 577–588

work page doi:10.1145/3477542 2021
[9]

Vida Dujmović, Gwenaël Joret, Piotr Micek, Pat Morin, Torsten Ueckerdt, and David R. Wood. Planar graphs have bounded queue-number.J. ACM, 67(4):22:1– 22:38, 2020.doi:10.1145/3385731. Preliminary version appeared in FOCS 2019, pages 862–875

work page doi:10.1145/3385731 2020
[10]

Dvoˇ r´ ak and R

Zdeněk Dvořák and Robin Thomas. List-coloring apex-minor-free graphs. arXiv:1401.1399, 2014.doi:10.48550/1401.1399

work page doi:10.48550/1401.1399 2014
[11]

1975 , url =

Peter Elias. Universal codeword sets and representations of the integers.IEEE Trans. Inf. Theory, 21(2):194–203, 1975.doi:10.1109/TIT.1975.1055349

work page doi:10.1109/tit.1975.1055349 1975
[12]

Shorter implicit representation for planar graphs and bounded treewidth graphs

Cyril Gavoille and Arnaud Labourel. Shorter implicit representation for planar graphs and bounded treewidth graphs. In Lars Arge, Michael Hoffmann, and Emo Welzl, editors,Proc. 15th Annual European Symposium on Algorithms(ESA 2007), vol- ume 4698 ofLecture Notes in Comput. Sci., pages 582–593. Springer, 2007.doi: 10.1007/978-3-540-75520-3_52

work page doi:10.1007/978-3-540-75520-3_52 2007
[13]

Simpler adjacency labeling for pla- nar graphs with B-trees

Pawel Gawrychowski and Wojciech Janczewski. Simpler adjacency labeling for pla- nar graphs with B-trees. In Karl Bringmann and Timothy M. Chan, editors,Proc. 5th Symposium on Simplicity in Algorithms(SOSA@SODA 2022), pages 24–36. SIAM, 2022.doi:10.1137/1.9781611977066.3

work page doi:10.1137/1.9781611977066.3 2022
[14]

Gilbert and Edward F

Edgar N. Gilbert and Edward F. Moore. Variable-length binary encodings.Bell System Technical Journal, 38(4):933–967, 1959.doi:10.1002/j.1538-7305.1959.tb01583. x

work page doi:10.1002/j.1538-7305.1959.tb01583 1959
[15]

Gilmore and Alan J

Paul C. Gilmore and Alan J. Hoffman. A characterization of comparability graphs and of interval graphs.Canadian J. Math., 16:539–548, 1964.doi:10.4153/ CJM-1964-055-5. 38

work page 1964
[16]

Tight pair query lower bounds for matching and earth mover’s distance

Maximilian Gorsky, Michal T. Seweryn, and Sebastian Wiederrecht. Polynomial bounds for the graph minor structure theorem. In66th Proc. IEEE Annual Sympo- sium on Foundations of Computer Science, FOCS 2025, pages 1961–1978. IEEE, 2025. doi:10.1109/FOCS63196.2025.00104

work page doi:10.1109/focs63196.2025.00104 2025
[17]

CoRRabs/2602.08734(2026)

Maximilian Gorsky, Michał T. Seweryn, and Sebastian Wiederrecht. The price of homogeneity is polynomial.arXiv:2602.01882, 2026.doi:10.48550/arXiv.2602. 01882

work page doi:10.48550/arxiv.2602 2026
[18]

Implicit representation of graphs

Sampath Kannan, Moni Naor, and Steven Rudich. Implicit representation of graphs. SIAM J. Discrete Math., 5(4):596–603, 1992.doi:10.1137/0405049. Preliminary ver- sion appeared in STOC 1988, pages 334–343

work page doi:10.1137/0405049 1992
[19]

Matthew Weinberg

Ken ichi Kawarabayashi, Robin Thomas, and Paul Wollan. A new proof of the flat wall theorem.J. Combinatorial Theory, Series B, 129:158–203, 2018.doi:10.1016/j. jctb.2017.09.002

work page doi:10.1016/j 2018
[20]

[Kur30] Kazimierz Kuratowski

Ken-ichi Kawarabayashi, Robin Thomas, and Paul Wollan. Quickly excluding a non- planar graph.arXiv:2010.12397, 2020.doi:10.48550/arXiv.2010.12397

work page doi:10.48550/arxiv.2010.12397 2010
[21]

Knuth.The Art of Computer Programming, Volume 3: Sorting and Searching

Donald E. Knuth.The Art of Computer Programming, Volume 3: Sorting and Searching. Addison-Wesley, 2nd edition, 1998

work page 1998
[22]

Kraft.A Device for Quantizing, Grouping, and Coding Amplitude Modulated Pulses

Leon G. Kraft.A Device for Quantizing, Grouping, and Coding Amplitude Modulated Pulses. Ms thesis, Massachusetts Institute of Technology, Cambridge, MA, 1949. Hdl:1721.1/12390

work page 1949
[23]

Nearly optimal binary search trees.Acta Informatica, 5(4):287–295, 1975.doi:10.1007/BF00264563

Kurt Mehlhorn. Nearly optimal binary search trees.Acta Informatica, 5(4):287–295, 1975.doi:10.1007/BF00264563

work page doi:10.1007/bf00264563 1975
[24]

Muller.Local Structure in Graph Classes

John H. Muller.Local Structure in Graph Classes. Ph.D. thesis, School of Information and Computer Science, Georgia Institute of Technology, 1988

work page 1988
[25]

C. St. J. A. Nash-Williams. Edge-disjoint spanning trees of finite graphs.J. London Math. Society, 36(1):445–450, 1961.doi:10.1112/jlms/s1-36.1.445

work page doi:10.1112/jlms/s1-36.1.445 1961
[26]

Spinrad.Efficient graph representations, volume 19 ofFields Institute mono- graphs

Jeremy P . Spinrad.Efficient graph representations, volume 19 ofFields Institute mono- graphs. American Mathematical Society, 2003. A Theorem 17 In this appendix, we review the labelling scheme of Dujmovićet al. [8] and its improve- ment by Gawrychowski and Janczewski [13] in order to show the existence of the weighted mixed labellings promised in Theorem...

work page 2003
[27]

The sequence of binary search treesT 1,

is approximately 2 √ logn, so that any root-to-leaf path inBcan be represented using logr+O( p logn) bits, for anyr∈ O(n). The sequence of binary search treesT 1, . . . , Th used in [13] is replaced with a sequence of B-treesB 1, . . . , Bh. For eachi∈ {1, . . . , h}, the leaves ofB i store the values inS + i . For each i∈ {1, . . . , h}, each vertex (v, ...

work page