Pith. sign in

REVIEW 5 minor 7 cited by

Graph classes through the lens of logic

T0 review · 0 major / 5 minor · reviewed 2026-08-10 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Graph classes can be ordered by whether one class can be FO-encoded in another, and this survey argues that this transduction order is the right lens for structural graph theory.

desk verdict A solid, honest survey that earns its place by framing structural graph theory through transductions; the load-bearing definitional choice is exposed but not deeply defended. read the letter →

arxiv 2501.04166 v1 pith:EMZOHTG4 submitted 2025-01-07 math.CO cs.DMcs.DScs.LO

Micha{l} Pilipczuk This is my paper · ORCID
classification math.COcs.DMcs.DScs.LO MSC 05C7503C13
keywords graphtransductionsmonadicstabilitydependencestructuraltheorynowheredensegraphsboundedexpansiontwin-widthFOideals
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This survey argues that first-order transductions are the right basic embedding relation for graph classes: a class D is no more complex than C when every graph in D can be produced from some colored graph in C by a fixed first-order formula and a restriction to an induced subgraph. Seen through this order, the classic sparse world (treedepth, treewidth, bounded expansion, nowhere denseness) and the model-theoretic dense world (monadic stability, monadic dependence, bounded twin-width) form one hierarchy, in which the sparse notions are exactly the weakly sparse instances of the logical ones. The survey's central proposal is that the boundary of first-order tractability is drawn by monadic dependence, and that the open Sparsification Conjecture—every monadically stable class is a transduction of a nowhere dense class—is the bridge that would complete the picture. A reader should come away seeing the transduction order not as a technical device but as a candidate organizing principle for structural graph theory itself.

What carries the argument

The central object is the FO transduction: arbitrarily add unary colors to the input graph, re-draw adjacency according to a fixed first-order formula, and then pass to an arbitrary induced subgraph. Composition of transductions makes them a quasi-order on graph classes, and downward-closed properties are the FO ideals of the theory. Two constructions generate the relevant ideals: forbidding transducibility of a pattern class (all graphs, or all half-graphs) yields monadic dependence and monadic stability; closing a sparse property under transductions yields structurally sparse classes. The flip operation—complementing all edges inside a chosen vertex set—acts as the dense analogue of vertex deletion and powers the Flipper game, flip-flatness, and flip-breakability that characterize the logical classes.

What would settle it

Exhibit a monadically stable graph class that is not FO-transducible from any nowhere dense graph class—for example, a class whose every bounded-depth quasi-bush representation has Gaifman graphs with unbounded depth-$h$ average degree $\nabla_h$; that would refute the Sparsification Conjecture and undercut the survey's proposed unification.

Watch

Extended reading notes

Core claim

The paper's central claim, assembled from the results it surveys, is that the transduction quasi-order $D \sqsubseteq_{\mathrm{FO}} C$ organizes the landscape of graph classes. Concretely, all the main non-sparse properties in its Figure 1—bounded shrubdepth, bounded (linear) cliquewidth, bounded twin-width, monadic stability, monadic dependence—are FO ideals, closed under transductions, while bounded treedepth, pathwidth, treewidth, bounded expansion, and nowhere denseness are their weakly sparse counterparts. The logical properties receive purely combinatorial characterizations: monadic stability is flip-flatness (Theorem 62), equivalently the bounded-round radius-$d$ Flipper game (Theorem 63); monadic dependence is flip-breakability (Theorem 70); nowhere dense classes are exactly weakly sparse monadically stable or dependent classes (Theorem 61). Monadic stability is known to make FO model checking fixed-parameter tractable (Theorem 69), while hereditary monadically independent classes are as hard as general graphs (Theorem 72). The survey presents the Sparsification Conjecture as the main open structural question: whether every monadically stable class is structurally nowhere dense, so that the dense logical world collapses onto sparse skeletons.

Load-bearing premise

The framework stands or falls with the choice in Section 2.3 to allow colorings but forbid multi-dimensional (copying or tuple) interpretations in transductions; if two-dimensional interpretations were allowed alongside colorings, edgeless graphs would transduce all graphs and the hierarchy would be trivial.

Editorial extensions

If this is right

  • Under the transduction order, bounded shrubdepth classes are the smallest FO ideal and monadically dependent classes the largest; every other discussed FO ideal sits between them.
  • Nowhere denseness is exactly the weakly sparse shadow of monadic dependence, and also of monadic stability, so any combinatorial handle on the dense notions automatically specializes to a sparse one.
  • Monadically stable classes admit fixed-parameter FO model checking, and the characterization via the Flipper game provides the decomposition that makes the algorithm go through.
  • Monadically dependent classes are the boundary of tractability for hereditary classes: any hereditary class that is not monadically dependent has FO model checking as hard as on all graphs.
  • If the Sparsification Conjecture is true, every monadically stable class can be represented as a transduction from a nowhere dense class, so the dense hierarchy is a logical dressing on sparse skeletons.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Editorial inference: the equivalence between monadic stability and flip-flatness suggests that flips, not deletions, are the correct local operation for dense graphs; one testable consequence is that algorithmic techniques built on deletions (splitter games, separators) should have flip-based analogues in dense classes.
  • Editorial inference: the survey's restriction to one-dimensional transductions is doing real work; any future extension to copying or multi-dimensional interpretations must be paired with a new restriction, otherwise the edgeless graph becomes universal and no hierarchy survives.
  • Editorial inference: the pattern dichotomy of Theorem 71 (star, clique, and half-graph crossings plus comparability grids) looks like a finite list of universal obstructions; one could try to turn it into an algorithm that, given a finite graph, either builds a bounded-round Flipper strategy or finds an induced pattern inside a bounded flip, giving a constructive test for monadic stability.
  • Editorial inference: the paper's Figure 1 could be read as a conjectural periodic table of structural graph theory; the place where new parameters (e.g., flips of twin-width or flip-width) should be inserted is determined by which pattern classes they forbid.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 5 minor

Summary. This survey develops the thesis that FO transductions provide a unifying embedding mechanism for structural graph theory. After introducing the logical and graph-theoretic background, it revisits classical parameters—treedepth, shrubdepth, treewidth/pathwidth, cliquewidth, twin-width, bounded expansion, and nowhere denseness—through their model-theoretic and transduction characterizations. It then presents more recent transduction-defined notions, in particular monadic stability, monadic dependence, and structurally sparse classes, and discusses algorithmic consequences such as FO model-checking. The survey is explicitly framed as an invitation to an emerging research programme rather than as a collection of new theorems, and it includes a large number of proof sketches, references, and open problems, including the Sparsification Conjecture.

Significance. If the survey is taken at face value, it is a timely and valuable synthesis of a fast-moving area. Its main contribution is organizational: it shows how the transduction viewpoint places otherwise disparate parameters in a common hierarchy, and it makes the central open problems precise. The paper is unusually transparent about its own conventions, especially the one-dimensional, non-copying definition of transductions in Section 2.3, and it explicitly warns that alternative conventions would lead to different theories. This transparency mitigates the main conceptual risk identified in the review process, namely that the 'new perspective' is definition-dependent rather than canonical. The survey is not a proof-heavy contribution, but for a journal survey this is appropriate, and the many proof sketches and references make it a useful entry point to the literature.

minor comments (5)
  1. [§3.3, proof of Theorem 36] The decomposition used in the proof of Theorem 36 is the Structure Theorem, i.e. Theorem 35; the text says 'the decomposition provided by Theorem 36' in two places. Please correct these cross-references.
  2. [§4.1.2, before Theorem 72] The sentence 'derive a complexity lower bound analogous to Theorem 72' precedes the statement of Theorem 72, making it a forward self-reference. It should presumably refer to Theorem 59, the monotone lower bound for non-nowhere-dense classes.
  3. [Abstract and §2.3] The narrative of the survey depends on the choice of one-dimensional, coloring-based, non-copying FO transductions. Since Section 2.3 correctly notes that alternative conventions are possible, I suggest adding a short clause in the abstract or Introduction signalling that the presented 'landscape' is relative to this convention.
  4. [§3.2.2, Theorem 32] The proof of the left-to-right implication says that classes of bounded cliquewidth are closed under CMSO-transductions, but Theorem 31 only states that they are MSO and FO ideals. Please either extend Theorem 31 to CMSO or provide a citation for this closure property.
  5. [§3.1.2, proof of Theorem 13] The phrase 'treedepth is a minor-monotone parameter' is slightly terse. It would be clearer to spell out that every graph in the original class is a minor of its 1-subdivision, so bounded treedepth of the subdivision class transfers back to the original class.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the transduction-based perspective is an openly stated organizing convention, and all substantive results are reported from external, independently developed proofs.

full rationale

The paper is a survey whose central claim is that first-order transductions offer a unifying perspective on graph classes. That claim functions as an expository thesis, not as a theorem derived from itself. The most delicate point is the definition of transduction in Section 2.3: one-dimensional FO interpretations on colored graphs, without copying. The survey is explicit that permitting both two-dimensional interpretations and colorings would make the class of all graphs transducible from edgeless graphs, 'making the notion trivial.' This is a candid statement of a modeling convention, not a disguised circular step: the paper does not use the convention to prove the convention, and it does not pretend the convention is forced. The substantive mathematical content is reported from external sources such as Theorems 9, 62, 69, and 76, with citations. Some of those sources include the author as a coauthor, which is normal for a survey of an active area; none of the self-citations is invoked as an unverified premise on which the survey's own conclusions rest. The paper's definitions are stipulative and its organizational claims are explicitly framed as a proposed research programme. No fitted parameter is renamed as a prediction, no uniqueness theorem is imported solely from the authors' prior work to forbid alternatives, and no known result is renamed in new coordinates and presented as a new derivation. The one-dimensionality restriction is a real limitation, but it is openly acknowledged and does not constitute circular reasoning.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

The survey introduces no free parameters or invented entities. Its load-bearing assumptions are the chosen definition of transductions and reliance on the correctness of the cited literature.

assumptions (3)
  • domain assumption All graphs are finite, undirected, and simple.
    Section 2.1 sets this scope; the theory of transductions is developed for this setting.
  • ad hoc to paper FO transductions are one-dimensional and do not include copying; multi-dimensional interpretations are disallowed.
    Section 2.3: the author restricts the definition to keep the theory non-trivial, noting that with two-dimensional interpretations and coloring, all graphs become transducible from edgeless graphs.
  • domain assumption All cited results are correct and appropriately attributed.
    The survey's narrative depends on dozens of external theorems such as Theorems 21, 32, 62, 69, and 76, and only sketches some proofs.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Graph classes through the lens of logic." pith.science (2026). https://pith.science/paper/EMZOHTG4

@misc{pith2026250104166,
  author       = {Pith},
  title        = {Pith review of: Graph classes through the lens of logic},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/EMZOHTG4}},
  note         = {Machine review of arXiv:2501.04166}
}
read the original abstract

Graph transformations definable in logic can be described using the notion of transductions. By understanding transductions as a basic embedding mechanism, which captures the possibility of encoding one graph in another graph by means of logical formulas, we obtain a new perspective on the landscape of graph classes and of their properties. The aim of this survey is to give a comprehensive presentation of this angle on structural graph theory. We first give a logic-focused overview of classic graph-theoretic concepts, such as treedepth, shrubdepth, treewidth, cliquewidth, twin-width, bounded expansion, and nowhere denseness. Then, we present recent developments related to notions defined purely through transductions, such as monadic stability, monadic dependence, and classes of structurally sparse graphs.

Figures

Figures reproduced from arXiv: 2501.04166 by the authors.

Figure 1
Figure 1. Major properties of graph classes discussed in this survey. All properties in the left-most column [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Transduction from the proof of Lemma 3. Left: a rook graph with colors A′ , B′ , and F depicted in red, yellow, and blue, respectively. Note that every row and every column is a clique, which is depicted using gray ovals. Right: the transduced bipartite graph. • The choice of transductions as the basic notion of embedding should not be regarded as the only correct one. For instance, the notion of logical intepretati… view at source ↗
Figure 3
Figure 3. Left: A graph (in black) together with its elimination tree of depth [PITH_FULL_IMAGE:figures/full_fig_p015_3.png] view at source ↗
Figures from the paper (8 more)
Figure 4
Figure 4. Figure 4: Applying a flip on a set A, depicted in yellow. SC-depth and Flipper Game. It is possible to define graph parameters that are applicable to single graphs, while being equivalent to shrubdepth in the following sense: they are bounded on the same classes of graphs. One s…
Figure 5
Figure 5. Figure 5: A half-graph of order 5. Proof. It is easy to transduce the class of paths from the class of half-graphs. As proved in [71], the class of paths has unbounded shrubdepth. Since classes of bounded shrubdepth are an FO ideal (Theorem 10), it follows that the class of half…
Figure 6
Figure 6. Figure 6: A graph and its tree decomposition of width [PITH_FULL_IMAGE:figures/full_fig_p021_6.png]
Figure 7
Figure 7. Figure 7: A 4 × 4 wall. and Seese [4]. Also, it has been investigated by Kreutzer and Tazari [94] that under relevant assump￾tions from parameterized complexity theory, the boundedness of treewidth is a necessary condition for statements like Theorem 21 to hold; see [94] for a p…
Figure 8
Figure 8. Figure 8: A somewhat artistic take on the decomposition provided by the Structure Theorem for minor-free [PITH_FULL_IMAGE:figures/full_fig_p028_8.png]
Figure 9
Figure 9. Figure 9: A contraction sequence of width 2 of a graph. The parts of the consecutive partitions are depicted in blue, the edges of the error graph are depicted in red. Proof sketch. Let T be a laminar decomposition of G of diversity k := mw(G). Let a front in T be a set of nodes…
Figure 10
Figure 10. Figure 10: A depth-1 minor model of K5. The idea is to consider classes of graphs that exclude complicated bounded-depth minors. There are two natural ways to understand the term “complicated”: either we exclude dense graphs, or we exclude com￾plete graphs. These two ways lead t…
Figure 11
Figure 11. Figure 11: The blue path witnesses that the yellow vertex is weakly [PITH_FULL_IMAGE:figures/full_fig_p038_11.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 7 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Set-defined graph classes: $\chi$-boundedness meets tropical algebra

    cs.DM 2026-07 accept novelty 8.0 of 10

    Full set-defined classes are polynomially χ-bounded iff they avoid high-chromatic shift graphs, decidable via tropical feasibility dual to mean-payoff games.

  2. The Erd\H{o}s-P\'{o}sa property for circle graphs as vertex-minors

    math.CO 2025-06 reject novelty 8.0 of 10

    For any circle graph H, every graph either has a vertex-minor isomorphic to k copies of H, or is a small perturbation of a graph with no H vertex-minor.

  3. First-order transducibility among classes of sparse graphs

    cs.LO 2025-05 accept novelty 8.0 of 10

    Treewidth t+1 graphs are not first-order transducible from treewidth t graphs, with analogous separations for Hadwiger number and for treewidth 4 graphs from planar graphs.

  4. Low rank MSO

    cs.LO 2025-02 accept novelty 8.0 of 10

    Low rank MSO, a restriction of MSO to bounded-cutrank set quantification, is expressively equivalent to flip-reachability logic on all undirected graphs, to separator logic on weakly sparse classes, and to flip-connec...

  5. k-Planar and Fan-Crossing Drawings and Transductions of Embeddable Graphs

    cs.CG 2025-06 conditional novelty 7.0 of 10

    Sparse graph classes are first-order transducible from graphs on a fixed surface if and only if they admit a new type of bounded fan-crossing drawing on that surface.

  6. Strong odd colorings in graph classes of bounded expansion

    math.CO 2025-05 conditional novelty 7.0 of 10

    Graph classes of bounded expansion have bounded strong odd chromatic number, and the same zero-or-odd property holds in balls of every fixed radius.

  7. Transductions of Graph Classes Admitting Product Structure

    cs.LO 2025-01 accept novelty 7.0 of 10

    Transductions of product-structured classes are, up to perturbation, exactly bounded path-power clique-width classes, which excludes 3D grids and pinned grid families.

Reference graph

Works this paper leans on

138 extracted references · 77 canonical work pages · cited by 7 Pith papers

  1. [1]

    Available online at https://warwick.ac.uk/fac/sci/maths/people/ staff/danielkral/alglogstr/openproblems.pdf

    Open problems from the workshop on algorithms, logic and structure, University of War- wick, 2016. Available online at https://warwick.ac.uk/fac/sci/maths/people/ staff/danielkral/alglogstr/openproblems.pdf

    2016

  2. [2]

    Adler and I

    H. Adler and I. Adler. Interpreting nowhere dense graph classes as a classical notion of model theory. European Journal of Combinatorics , 36:322–330, 2014

    2014

  3. [3]

    Archdeacon

    D. Archdeacon. A Kuratowski theorem for the projective plane. Journal of Graph Theory , 5(3):243– 246, 1981

    1981

  4. [4]

    Arnborg, J

    S. Arnborg, J. Lagergren, and D. Seese. Easy problems for tree-decomposable graphs. Journal of Algorithms, 12(2):308–340, 1991

    1991

  5. [5]

    Atminas, V

    A. Atminas, V. V. Lozin, and I. Razgon. Linear time algorithm for computing a small biclique in graphs without long induced paths. In 13th Scandinavian Symposium and Workshops on Algorithm Theory, SW AT 2012, volume 7357 ofLecture Notes in Computer Science, pages 142–152. Springer, 2012

    2012

  6. [6]

    Atserias, A

    A. Atserias, A. Dawar, and M. Grohe. Preservation under extensions on well-behaved finite struc- tures. SIAM Journal on Computing , 38(4):1364–1381, 2008

    2008

  7. [7]

    Atserias, A

    A. Atserias, A. Dawar, and P. G. Kolaitis. On preservation under homomorphisms and unions of conjunctive queries. Journal of the ACM, 53(2):208–237, 2006

    2006

  8. [8]

    J. T. Baldwin and S. Shelah. Second-order quantifiers and the complexity of theories. Notre Dame Journal of Formal Logic , 26(3):229–303, 1985

    1985

Show all 138 references
  1. [9]

    Blumensath and B

    A. Blumensath and B. Courcelle. On the Monadic Second-Order transduction hierarchy. Logical Methods in Computer Science , 6(2), 2010

    2010

  2. [10]

    H. L. Bodlaender. A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM Journal on Computing, 25(6):1305–1317, 1996

    1996

  3. [11]

    Bollob ´as and A

    B. Bollob ´as and A. Thomason. Proof of a conjecture of Mader, Erd ¨os and Hajnal on topological complete subgraphs. European Journal of Combinatorics , 19(8):883–887, 1998

    1998

  4. [12]

    Bonamy, ´E

    M. Bonamy, ´E. Bonnet, H. D ´epr´es, L. Esperet, C. Geniet, C. Hilaire, S. Thomass ´e, and A. Wesolek. Sparse graphs with bounded induced cycle packing number have logarithmic treewidth. Journal of Combinatorial Theory, Series B, 167:215–249, 2024

    2024

  5. [13]

    Bonnet, J

    ´E. Bonnet, J. Dreier, J. Gajarsk ´y, S. Kreutzer, N. M ¨ahlmann, P. Simon, and Sz. Toru ´nczyk. Model checking on interpretations of classes of bounded local cliquewidth. In 37th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2022 , pages 54:1–54:13. ACM, 2022

    2022

  6. [14]

    Bonnet, F

    ´E. Bonnet, F. Foucaud, T. Lehtil¨a, and A. Parreau. Neighbourhood complexity of graphs of bounded twin-width. European Journal of Combinatorics , 115:103772, 2024

    2024

  7. [15]

    Bonnet, C

    ´E. Bonnet, C. Geniet, E. J. Kim, S. Thomass´e, and R. Watrigant. Twin-width II: small classes. In 32nd ACM-SIAM Symposium on Discrete Algorithms, SODA 2021 , pages 1977–1996. SIAM, 2021. 59

    2021

  8. [16]

    Bonnet, C

    ´E. Bonnet, C. Geniet, E. J. Kim, S. Thomass ´e, and R. Watrigant. Twin-width III: Max Independent Set, Min Dominating Set, and Coloring. In 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021 , volume 198 of LIPIcs, pages 35:1–35:20. Schloss Dags...

    2021

  9. [17]

    Bonnet, U

    ´E. Bonnet, U. Giocanti, P. Ossona de Mendez, P. Simon, S. Thomass´e, and Sz. Toru´nczyk. Twin-width IV: Ordered graphs and matrices. Journal of the ACM, 71(3):21, 2024

    2024

  10. [18]

    Bonnet, E

    ´E. Bonnet, E. J. Kim, A. Reinald, and S. Thomass´e. Twin-width VI: the lens of contraction sequences. In 33rd ACM-SIAM Symposium on Discrete Algorithms, SODA 2022 , pages 1036–1056. SIAM, 2022

    2022

  11. [19]

    Bonnet, E

    ´E. Bonnet, E. J. Kim, A. Reinald, S. Thomass´e, and R. Watrigant. Twin-width and polynomial kernels. Algorithmica, 84(11):3300–3337, 2022

    2022

  12. [20]

    Bonnet, E

    ´E. Bonnet, E. J. Kim, S. Thomass ´e, and R. Watrigant. Twin-width I: Tractable FO Model Checking. Journal of the ACM, 69(1):3:1–3:46, 2022

    2022

  13. [21]

    A. Bouchet. Circle graph obstructions. Journal of Combinatoral Theory, Series B, 60(1):107–144, 1994

    1994

  14. [22]

    Braunfeld, A

    S. Braunfeld, A. Dawar, I. Eleftheriadis, and A. Papadopoulos. Monadic NIP in monotone classes of relational structures. In 50th International Colloquium on Automata, Languages, and Program- ming, ICALP 2023 , volume 261 of LIPIcs, pages 119:1–119:18. Schloss Dagstuhl — Leibni...

    2023

  15. [23]

    Braunfeld, J

    S. Braunfeld, J. Ne ˇsetˇril, P. Ossona de Mendez, and S. Siebertz. Decomposition horizons: from graph sparsity to model-theoretic dividing lines. CoRR, abs/2209.11229, 2022

    2022 arXiv

  16. [24]

    Braunfeld, J

    S. Braunfeld, J. Ne ˇsetˇril, P. Ossona de Mendez, and S. Siebertz. On the first-order transduction quasiorder of hereditary classes of graphs. CoRR, abs/2208.14412, 2022

    2022 arXiv

  17. [25]

    Buffi `ere, E

    H. Buffi `ere, E. Kim, and P. Ossona de Mendez. Shallow vertex minors, stability, and dependence. Innovations in Graph Theory , 1:87–112, 2024

    2024

  18. [26]

    J. Chen, W. Czerwi ´nski, Y. Disser, A. E. Feldmann, D. Hermelin, W. Nadara, Ma. Pilipczuk, Mi. Pilipczuk, M. Sorge, B. Wr ´oblewski, and A. Zych-Pawlewicz. Efficient fully dynamic elimi- nation forests with applications to detecting long paths and cycles. In 32nd ACM-SIAM Sym...

    2021

  19. [27]

    Chen and J

    Y. Chen and J. Flum. FO-definability of shrub-depth. In 28th EACSL Annual Conference on Computer Science Logic, CSL 2020, volume 152 ofLIPIcs, pages 15:1–15:16. Schloss Dagstuhl — Leibniz-Zentrum f¨ur Informatik, 2020

    2020

  20. [28]

    Colcombet

    T. Colcombet. A combinatorial theorem for trees. In 34th International Colloquium on Automata, Languages and Programming, ICALP 2007 , volume 4596 of Lecture Notes in Computer Science , pages 901–912. Springer, 2007

    2007

  21. [29]

    Courcelle

    B. Courcelle. The Monadic Second-Order logic of graphs. I. Recognizable sets of finite graphs. In- formation and Computation, 85(1):12–75, 1990

    1990

  22. [30]

    Courcelle and J

    B. Courcelle and J. Engelfriet. Graph Structure and Monadic Second-Order Logic — A Language- Theoretic Approach, volume 138 of Encyclopedia of mathematics and its applications . Cambridge Uni- versity Press, 2012. 60

    2012

  23. [31]

    Courcelle, J

    B. Courcelle, J. Engelfriet, and G. Rozenberg. Handle-rewriting hypergraph grammars. Journal of Computer and System Sciences , 46(2):218–270, 1993

    1993

  24. [32]

    Courcelle, J

    B. Courcelle, J. A. Makowsky, and U. Rotics. Linear time solvable optimization problems on graphs of bounded clique-width. Theory of Computing Systems , 33(2):125–150, 2000

    2000

  25. [33]

    Courcelle and S

    B. Courcelle and S. Olariu. Upper bounds to the clique width of graphs.Discrete Applied Mathematics, 101(1-3):77–114, 2000

    2000

  26. [34]

    Courcelle and S

    B. Courcelle and S. Oum. Vertex-minors, monadic second-order logic, and a conjecture by Seese. Journal of Combinatorial Theory, Series B , 97(1):91–126, 2007

    2007

  27. [35]

    Cygan, F

    M. Cygan, F. V. Fomin, Ł. Kowalik, D. Lokshtanov, D. Marx, Ma. Pilipczuk, Mi. Pilipczuk, and S. Saurabh. Parameterized Algorithms. Springer, 2015

    2015

  28. [36]

    A. Dawar. Finite model theory on tame classes of structures. In 32nd International Symposium on Mathematical Foundations of Computer Science 2007, MFCS 2007 , volume 4708 of Lecture Notes in Computer Science, pages 2–12. Springer, 2007

    2007

  29. [37]

    A. Dawar. Homomorphism preservation on quasi-wide classes. Journal of Computer and System Sciences, 76(5):324–332, 2010

    2010

  30. [38]

    A. Dawar. Corrigendum to ”Homomorphism preservation on quasi-wide classes” [J. Comput. Syst. Sci. 76 (5) (2010) 324-332]. Journal of Computer and System Sciences , 145:103553, 2024

    2010

  31. [39]

    Dawar and S

    A. Dawar and S. Kreutzer. Domination problems in nowhere-dense classes. In 29th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2009 , volume 4 of LIPIcs, pages 157–168. Schloss Dagstuhl — Leibniz-Zentrum f¨ur Informatik, 2009

    2009

  32. [40]

    Diestel, K

    R. Diestel, K. Kawarabayashi, T. M ¨uller, and P. Wollan. On the excluded minor structure theorem for graphs of large tree-width. Journal of Combinatorial Theory, Series B , 102(6):1189–1210, 2012

    2012

  33. [41]

    G. Ding. Subgraphs and well-quasi-ordering. Journal of Graph Theory , 16(5):489–502, 1992

    1992

  34. [42]

    J. Dreier. Lacon-, shrub- and parity-decompositions: Characterizing transductions of bounded ex- pansion classes. Logical Methods in Computer Science , 19(2), 2023

    2023

  35. [43]

    Dreier, I

    J. Dreier, I. Eleftheriadis, N. M ¨ahlmann, R. McCarty, Mi. Pilipczuk, and Sz. Toru ´nczyk. First-Order model checking on monadically stable graph classes. In65th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2024 , pages 21–30. IEEE, 2024

    2024

  36. [44]

    Dreier, J

    J. Dreier, J. Gajarsk ´y, Y. Jiang, P. Ossona de Mendez, and J. Raymond. Twin-width and generalized coloring numbers. Discrete Mathematics, 345(3):112746, 2022

    2022

  37. [45]

    Dreier, J

    J. Dreier, J. Gajarsk ´y, Y. Jiang, P. Ossona de Mendez, and J. Raymond. Corrigendum to ”Twin-width and generalized coloring numbers” [Discrete Math. 345 (3) (2022) 112746]. Discrete Mathematics, 347(1):113750, 2024

    2022

  38. [46]

    Dreier, J

    J. Dreier, J. Gajarsk ´y, S. Kiefer, Mi. Pilipczuk, and Sz. Toru´nczyk. Treelike decompositions for trans- ductions of sparse graphs. In 37th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2022, pages 31:1–31:14. ACM, 2022. 61

    2022

  39. [47]

    Dreier, N

    J. Dreier, N. M ¨ahlmann, and S. Siebertz. First-Order model checking on structurally sparse graph classes. In 55th Annual ACM Symposium on Theory of Computing, STOC 2023 , pages 567–580. ACM, 2023

    2023

  40. [48]

    Dreier, N

    J. Dreier, N. M ¨ahlmann, S. Siebertz, and Sz. Toru ´nczyk. Indiscernibles and flatness in monadically stable and monadically NIP classes. In 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023 , volume 261 of LIPIcs, pages 125:1–125:18. Schloss D...

    2023

  41. [49]

    Dreier, N

    J. Dreier, N. M¨ahlmann, and Sz. Toru´nczyk. Flip-breakability: A combinatorial dichotomy for monad- ically dependent graph classes. In 56th Annual ACM Symposium on Theory of Computing, STOC 2024, pages 1550–1560. ACM, 2024

    2024

  42. [50]

    Duron, L

    J. Duron, L. Esperet, and J.-F. Raymond. Long induced paths in sparse graphs and graphs with forbidden patterns. CoRR, abs/2411.08685, 2024

    2024 arXiv

  43. [51]

    Dvo ˇr´ak

    Z. Dvo ˇr´ak. Asymptotical structure of combinatorial objects . PhD thesis, Charles University, Faculty of Mathematics and Physics, 2007

    2007

  44. [52]

    Dvo ˇr´ak

    Z. Dvo ˇr´ak. Constant-factor approximation of the domination number in sparse graphs. European Journal of Combinatorics, 34(5):833–840, 2013

    2013

  45. [53]

    Dvo ˇr´ak

    Z. Dvo ˇr´ak. Induced subdivisions and bounded expansion. European Journal of Combinatorics , 69:143–148, 2018

    2018

  46. [54]

    Dvo ˇr´ak, A

    Z. Dvo ˇr´ak, A. C. Giannopoulou, and D. M. Thilikos. Forbidden graphs for tree-depth. European Journal of Combinatorics, 33(5):969–979, 2012

    2012

  47. [55]

    Dvo ˇr´ak, D

    Z. Dvo ˇr´ak, D. Kr´al’, and R. Thomas. Testing first-order properties for subclasses of sparse graphs. Journal of the ACM, 60(5):36:1–36:24, 2013

    2013

  48. [56]

    Eickmeyer, A

    K. Eickmeyer, A. C. Giannopoulou, S. Kreutzer, O. Kwon, Mi. Pilipczuk, R. Rabinovich, and S. Siebertz. Neighborhood complexity and kernelization for nowhere dense classes of graphs. In 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017 , volume 8...

    2017

  49. [57]

    Elberfeld, M

    Mi. Elberfeld, M. Grohe, and T. Tantau. Where First-Order and Monadic Second-Order logic coincide. ACM Transactions on Computational Logic , 17(4):25, 2016

    2016

  50. [58]

    Flum and M

    J. Flum and M. Grohe. Fixed-parameter tractability, definability, and model-checking. SIAM Journal on Computing, 31(1):113–145, 2001

    2001

  51. [59]

    Flum and M

    J. Flum and M. Grohe. Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2006

    2006

  52. [60]

    Frick and M

    M. Frick and M. Grohe. Deciding first-order properties of locally tree-decomposable structures. Journal of the ACM, 48(6):1184–1206, 2001

    2001

  53. [61]

    H. Gaifman. On local and non-local properties. Studies in Logic and the Foundations of Mathematics , 107:105–135, 1982

    1982

  54. [62]

    Gajarsk ´y, M

    J. Gajarsk ´y, M. Gorsky, and S. Kreutzer. Differential games, locality, and model checking for FO logic of graphs. In 30th EACSL Annual Conference on Computer Science Logic, CSL 2022 , volume 216 of LIPIcs, pages 22:1–22:18. Schloss Dagstuhl — Leibniz-Zentrum f¨ur Informatik,...

    2022

  55. [63]

    Gajarsk ´y and P

    J. Gajarsk ´y and P. Hlin ˇen´y. Kernelizing MSO properties of trees of fixed height, and some conse- quences. Logical Methods in Computer Science , 11(1), 2015

    2015

  56. [64]

    Gajarsk ´y, P

    J. Gajarsk ´y, P. Hlinˇen´y, J. Obdrˇz´alek, D. Lokshtanov, and M. S. Ramanujan. A new perspective on FO model checking of dense graph classes. ACM Transactions on Computational Logic, 21(4):28:1–28:23, 2020

    2020

  57. [65]

    Gajarsk ´y, S

    J. Gajarsk ´y, S. Kreutzer, J. Ne ˇsetˇril, P. Ossona de Mendez, Mi. Pilipczuk, S. Siebertz, and Sz. Toru ´nczyk. First-order interpretations of bounded expansion classes. ACM Transactions on Computational Logic, 21(4):29:1–29:41, 2020

    2020

  58. [66]

    Gajarsk ´y, M

    J. Gajarsk ´y, M. Lampis, and S. Ordyniak. Parameterized algorithms for modular-width. In 8th International Symposium Parameterized and Exact Computation, IPEC 2013 , volume 8246 of Lecture Notes in Computer Science , pages 163–176. Springer, 2013

    2013

  59. [67]

    Gajarsk ´y, N

    J. Gajarsk ´y, N. M ¨ahlmann, R. McCarty, P. Ohlmann, Mi. Pilipczuk, W. Przybyszewski, S. Siebertz, M. Sokołowski, and Sz. Toru ´nczyk. Flipper games for monadically stable graph classes. In 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023 , vo...

    2023

  60. [68]

    Gajarsk ´y, Mi

    J. Gajarsk ´y, Mi. Pilipczuk, W. Przybyszewski, and Sz. Toru ´nczyk. Twin-width and types. In 49th International Colloquium on Automata, Languages, and Programming, ICALP 2022 , volume 229 of LIPIcs, pages 123:1–123:21. Schloss Dagstuhl — Leibniz-Zentrum f¨ur Informatik, 2022

    2022

  61. [69]

    Gajarsk ´y, Mi

    J. Gajarsk ´y, Mi. Pilipczuk, and Sz. Toru´nczyk. Stable graphs of bounded twin-width. In 37th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2022 , pages 39:1–39:12. ACM, 2022

    2022

  62. [70]

    Galvin, I

    F. Galvin, I. Rival, and B. Sands. A Ramsey-type theorem for traceable graphs. Journal of Combina- torial Theory, Series B, 33(1):7–16, 1982

    1982

  63. [71]

    Ganian, P

    R. Ganian, P. Hlin ˇen´y, J. Neˇsetˇril, J. Obdrˇz´alek, and P. Ossona de Mendez. Shrub-depth: Capturing height of dense graphs. Logical Methods in Computer Science , 15(1), 2019

    2019

  64. [72]

    Ganian, P

    R. Ganian, P. Hlin ˇen´y, J. Neˇsetˇril, J. Obdrˇz´alek, P. Ossona de Mendez, and R. Ramadurai. When trees grow low: Shrubs and fast MSO 1. In 37th International Symposium on Mathematical Foundations of Computer Science 2012, MFCS 2012, volume 7464 ofLecture Notes in Computer ...

    2012

  65. [73]

    Geelen, B

    J. Geelen, B. Gerards, and G. Whittle. Excluding a planar graph from GF (q)-representable matroids. Journal of Combinatorial Theory, Series B , 97(6):971–998, 2007

    2007

  66. [74]

    Geelen, O

    J. Geelen, O. Kwon, R. McCarty, and P. Wollan. The Grid Theorem for vertex-minors. Journal of Combinatorial Theory, Series B, 158(Part):93–116, 2023

    2023

  67. [75]

    H. H. Glover, J. P. Huneke, and C. S. Wang. 103 graphs that are irreducible for the projective plane. Journal of Combinatorial Theory, Series B , 27(3):332–370, 1979

    1979

  68. [76]

    M. Grohe. Local tree-width, excluded minors, and approximation algorithms. Combinatorica, 23(4):613–632, 2003

    2003

  69. [77]

    Grohe and S

    M. Grohe and S. Kreutzer. Methods for algorithmic meta theorems. Model Theoretic Methods in Finite Combinatorics, 558:181–206, 2011. 63

    2011

  70. [78]

    Grohe, S

    M. Grohe, S. Kreutzer, R. Rabinovich, S. Siebertz, and K. S. Stavropoulos. Coloring and covering nowhere dense graphs. SIAM Journal on Discrete Mathematics , 32(4):2467–2481, 2018

    2018

  71. [79]

    Grohe, S

    M. Grohe, S. Kreutzer, and S. Siebertz. Deciding first-order properties of nowhere dense graphs. Journal of the ACM, 64(3):17:1–17:32, 2017

    2017

  72. [80]

    Guillemot and D

    S. Guillemot and D. Marx. Finding small patterns in permutations in linear time. In 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014 , pages 82–101. SIAM, 2014

    2014

  73. [81]

    Hlin ˇen´y and J

    P. Hlin ˇen´y and J. Jedelsk ´y. Twin-width of planar graphs is at most 8, and at most 6 when bipartite planar. In 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023 , volume 261 of LIPIcs, pages 75:1–75:18. Schloss Dagstuhl — Leibniz-Zentrum f¨u...

    2023

  74. [82]

    Hlin ˇen´y, F

    P. Hlin ˇen´y, F. Pokr ´yvka, and B. Roy. FO model checking on geometric graphs. Computational Geometry, 78:1–19, 2019

    2019

  75. [83]

    Hunter, A

    Z. Hunter, A. Milojevi ´c, B. Sudakov, and I. Tomon. Long induced paths in Ks,s-free graphs. CoRR, abs/2411.19173, 2024

    2024 arXiv

  76. [84]

    Kazana and L

    W. Kazana and L. Segoufin. First-order queries on classes of structures with bounded expansion. Logical Methods in Computer Science , 16(1), 2020

    2020

  77. [85]

    H. A. Kierstead and D. Yang. Orderings on graphs and game coloring number. Order, 20(3):255–264, 2003

    2003

  78. [86]

    Kim and S

    D. Kim and S. Oum. Vertex-minors of graphs: A survey. Discrete Applied Mathematics, 351:54–73, 2024

    2024

  79. [87]

    Koml ´os and E

    J. Koml ´os and E. Szemer´edi. Topological cliques in graphs.Combinatorics, Probability and Computing, 3:247–256, 1994

    1994

  80. [88]

    Korhonen

    T. Korhonen. A single-exponential time 2-approximation algorithm for treewidth. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021 , pages 184–192. IEEE, 2021

    2021

  81. [89]

    Korhonen

    T. Korhonen. Grid induced minor theorem for graphs of small degree. Journal of Combinatorial Theory, Series B, 160:206–214, 2023

    2023

  82. [90]

    Korhonen and D

    T. Korhonen and D. Lokshtanov. An improved parameterized algorithm for treewidth. In55th Annual ACM Symposium on Theory of Computing, STOC 2023 , pages 528–541. ACM, 2023

    2023

  83. [91]

    Korhonen and M

    T. Korhonen and M. Sokołowski. Almost-linear time parameterized algorithm for rankwidth via dynamic rankwidth. In 56th Annual ACM Symposium on Theory of Computing, STOC 2024 , pages 1538–1549. ACM, 2024

    2024

  84. [92]

    A. V. Kostochka. Lower bound of the Hadwiger number of graphs by their average degree. Combi- natorics, 4(4):307–316, 1984

    1984

  85. [93]

    Kr ´al’ and A

    D. Kr ´al’ and A. Lamaison. Planar graph with twin-width seven. European Journal of Combinatorics, In press:103749, 2023

    2023

  86. [94]

    Kreutzer and S

    S. Kreutzer and S. Tazari. Lower bounds for the complexity of Monadic Second-Order logic. In 25th Annual IEEE Symposium on Logic in Computer Science, LICS 2010 , pages 189–198. IEEE Computer Society, 2010. 64

    2010

  87. [95]

    Kufleitner

    M. Kufleitner. The height of factorization forests. In 33rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2008, volume 5162 ofLecture Notes in Computer Science, pages 443–454. Springer, 2008

    2008

  88. [96]

    Kuratowski

    K. Kuratowski. Sur le probl `eme des courbes gauches en topologie. Fundamenta Mathematicae , 15:271–283, 1930. In French

    1930

  89. [97]

    Lagergren

    J. Lagergren. Upper bounds on the size of obstructions and intertwines. Journal of Combinatorial Theory, Series B, 73(1):7–40, 1998

    1998

  90. [98]

    Marcus and G

    A. Marcus and G. Tardos. Excluded permutation matrices and the Stanley-Wilf conjecture. Journal of Combinatorial Theory, Series A , 107(1):153–160, 2004

    2004

  91. [99]

    Ne ˇsetˇril and P

    J. Ne ˇsetˇril and P. Ossona de Mendez. Tree-depth, subgraph coloring and homomorphism bounds. European Journal of Combinatorics , 27(6):1022–1041, 2006

    2006

  92. [100]

    Ne ˇsetˇril and P

    J. Ne ˇsetˇril and P. Ossona de Mendez. Grad and classes with bounded expansion I. Decompositions. European Journal of Combinatorics , 29(3):760–776, 2008

    2008

  93. [101]

    Ne ˇsetˇril and P

    J. Ne ˇsetˇril and P. Ossona de Mendez. Grad and classes with bounded expansion II. Algorithmic aspects. European Journal of Combinatorics , 29(3):777–791, 2008

    2008

  94. [102]

    Ne ˇsetˇril and P

    J. Ne ˇsetˇril and P. Ossona de Mendez. Grad and classes with bounded expansion III. Restricted graph homomorphism dualities. European Journal of Combinatorics , 29(4):1012–1024, 2008

    2008

  95. [103]

    Ne ˇsetˇril and P

    J. Ne ˇsetˇril and P. Ossona de Mendez. First order properties on nowhere dense structures. Journal of Symbolic Logic, 75(3):868–887, 2010

    2010

  96. [104]

    Ne ˇsetˇril and P

    J. Ne ˇsetˇril and P. Ossona de Mendez. On nowhere dense graphs. European Journal of Combinatorics, 32(4):600–617, 2011

    2011

  97. [105]

    Ne ˇsetˇril and P

    J. Ne ˇsetˇril and P. Ossona de Mendez. Sparsity — Graphs, Structures, and Algorithms , volume 28 of Algorithms and combinatorics. Springer, 2012

    2012

  98. [106]

    Ne ˇsetˇril, P

    J. Ne ˇsetˇril, P. Ossona de Mendez, Mi. Pilipczuk, R. Rabinovich, and S. Siebertz. Rankwidth meets stability. In 32nd ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, pages 2014–2033. SIAM, 2021

    2021

  99. [107]

    Ne ˇsetˇril, P

    J. Ne ˇsetˇril, P. Ossona de Mendez, R. Rabinovich, and S. Siebertz. Classes of graphs with low com- plexity: The case of classes with bounded linear rankwidth. European Journal of Combinatorics , 91:103223, 2021

    2021

  100. [108]

    Ne ˇsetˇril, P

    J. Ne ˇsetˇril, P. Ossona de Mendez, and S. Siebertz. Structural properties of the First-Order transduction quasiorder. In 30th EACSL Annual Conference on Computer Science Logic, CSL 2022 , volume 216 of LIPIcs, pages 31:1–31:16. Schloss Dagstuhl — Leibniz-Zentrum f¨ur Informa...

    2022

  101. [109]

    Ne ˇsetˇril, P

    J. Ne ˇsetˇril, P. Ossona de Mendez, and S. Siebertz. Modulo-counting first-order logic on bounded expansion classes. Discrete Mathematics, 347(8):113700, 2024

    2024

  102. [110]

    Ossona de Mendez

    P. Ossona de Mendez. First-Order transductions of graphs (invited talk). In 38th International Sym- posium on Theoretical Aspects of Computer Science, STACS 2021 , volume 187 of LIPIcs, pages 2:1–2:7. Schloss Dagstuhl — Leibniz-Zentrum f¨ur Informatik, 2021. 65

    2021

  103. [111]

    Ossona de Mendez, Mi

    P. Ossona de Mendez, Mi. Pilipczuk, and S. Siebertz. Transducing paths in graph classes with un- bounded shrubdepth. European Journal of Combinatorics , In Press:103660, 2022

    2022

  104. [112]

    Oum and P

    S. Oum and P. D. Seymour. Approximating clique-width and branch-width.Journal of Combinatorial Theory, Series B, 96(4):514–528, 2006

    2006

  105. [113]

    Sparsity

    Ma. Pilipczuk, Mi. Pilipczuk, and S. Siebertz. Lecture notes for the course “Sparsity” given at Faculty of Mathematics, Informatics, and Mechanics of the University of Warsaw, Winter semesters 2017/18 and 2019/20. Available online at https://www.mimuw.edu.pl/ mp248287/sparsity2

    2017

  106. [114]

    Pilipczuk, S

    Mi. Pilipczuk, S. Siebertz, and Sz. Toru ´nczyk. Parameterized circuit complexity of model-checking on sparse structures. In 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2018 , pages 789–798. ACM, 2018

    2018

  107. [115]

    A. Pillay. Introduction to Stability Theory . Dover Books on Mathematics. Dover Publications, 2008

    2008

  108. [116]

    Podewski and M

    K.-P. Podewski and M. Ziegler. Stable graphs. Fundamenta Mathematicae, 100(2):101–107, 1978

    1978

  109. [117]

    Przybyszewski

    W. Przybyszewski. Distal combinatorial tools for graphs of bounded twin-width. In 38th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2023 , pages 1–13. IEEE, 2023

    2023

  110. [118]

    M. Rao. Clique-width of graphs defined by one-vertex extensions. Discrete Mathematics , 308(24):6157–6165, 2008

    2008

  111. [119]

    Reidl, P

    F. Reidl, P. Rossmanith, F. S ´anchez Villaamil, and S. Sikdar. A faster parameterized algorithm for treedepth. In 41st International Colloquium on Automata, Languages, and Programming, ICALP 2014 , volume 8572 of Lecture Notes in Computer Science , pages 931–942. Springer, 2014

    2014

  112. [120]

    Reidl, F

    F. Reidl, F. S ´anchez Villaamil, and K. S. Stavropoulos. Characterising bounded expansion by neigh- bourhood complexity. European Journal of Combinatorics , 75:152–168, 2019

    2019

  113. [121]

    Robertson and P

    N. Robertson and P. D. Seymour. Graph Minors. I. Excluding a forest. Journal of Combinatorial Theory, Series B, 35(1):39–61, 1983

    1983

  114. [122]

    Robertson and P

    N. Robertson and P. D. Seymour. Graph Minors. II. Algorithmic aspects of tree-width. Journal of Algorithms, 7(3):309–322, 1986

    1986

  115. [123]

    Robertson and P

    N. Robertson and P. D. Seymour. Graph Minors. V. Excluding a planar graph. Journal of Combina- torial Theory, Series B, 41(1):92–114, 1986

    1986

  116. [124]

    Robertson and P

    N. Robertson and P. D. Seymour. Graph Minors. XIII. The Disjoint Paths problem. Journal of Com- binatorial Theory, Series B, 63(1):65–110, 1995

    1995

  117. [125]

    Robertson and P

    N. Robertson and P. D. Seymour. Graph Minors. XVI. Excluding a non-planar graph. Journal of Combinatorial Theory, Series B, 89(1):43–76, 2003

    2003

  118. [126]

    Robertson and P

    N. Robertson and P. D. Seymour. Graph Minors. XX. Wagner’s conjecture. Journal of Combinatorial Theory, Series B, 92(2):325–357, 2004

    2004

  119. [127]

    N. Sauer. On the density of families of sets. Journal of Combinatorial Theory, Series A, 13(1):145–147, 1972

    1972

  120. [128]

    P. D. Seymour. A bound on the excluded minors for a surface, 1993. Unpublished manuscript, available at https://web.math.princeton.edu/ pds/papers/surfacebound/bound.pdf. 66

    1993

  121. [129]

    S. Shelah. A combinatorial problem; stability and order for models and theories in infinitary lan- guages. Pacific Journal of Mathematics , 41(1):247–261, 1972

    1972

  122. [130]

    S. Shelah. Classification theory: and the number of non-isomorphic models . Elsevier, 1990

    1990

  123. [131]

    I. Simon. Factorization forests of finite height. Theoretical Computer Science, 72(1):65–94, 1990

    1990

  124. [132]

    Tent and M

    K. Tent and M. Ziegler. A Course in Model Theory . Lecture Notes in Logic. Cambridge University Press, 2012

    2012

  125. [133]

    Toru ´nczyk

    Sz. Toru ´nczyk. Aggregate queries on sparse databases. In 39th ACM SIGMOD-SIGACT-SIGAI Sym- posium on Principles of Database Systems, PODS 2020 , pages 427–443. ACM, 2020

    2020

  126. [134]

    Toru ´nczyk

    Sz. Toru ´nczyk. Flip-width: Cops and Robber on dense graphs. In 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023 , pages 663–700. IEEE, 2023

    2023

  127. [135]

    K. Wagner. ¨Uber eine Eigenschaft der ebenen Komplexe.Mathematische Annalen, 114:570–590, 1937. In German

    1937

  128. [136]

    E. Wanke. k-NLC graphs and polynomial algorithms.Discrete Applied Mathematics, 54(2-3):251–266, 1994

    1994

  129. [137]

    E. Welzl. Partition trees for triangle counting and other range searching problems. In 4th Annual Symposium on Computational Geometry, SoCG 1988 , pages 23–33. ACM, 1988

    1988

  130. [138]

    X. Zhu. Colouring graphs with bounded generalized colouring number. Discrete Mathematics , 309(18):5562–5568, 2009. 67

    2009

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.