pith. sign in

arxiv: 2604.19138 · v1 · submitted 2026-04-21 · 💻 cs.DS · cs.DM· math.CO

Moderately beyond clique-width: reduced component max-leaf and related parameters

\'Edouard Bonnet , Yeonsu Chang , Julien Duron , Colin Geniet , O-joung Kwon This is my paper

Pith reviewed 2026-05-10 02:05 UTC · model grok-4.3

classification 💻 cs.DS cs.DMmath.CO
keywords graph parametersclique-widthcontraction sequencesinduced subgraphstreewidthunit interval graphsplanar graphsfirst-order transductions
0
0 comments X

The pith

Reduced component max-leaf is a graph parameter strictly between clique-width and reduced bandwidth that supports polynomial algorithms for induced subgraph problems when a contraction sequence is given.

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

The paper defines reduced component max-leaf through contraction sequences as the maximum number of leaves appearing in any spanning tree of any connected component. It shows this value lies strictly above clique-width but below reduced bandwidth, remains bounded on unit interval graphs, and grows without bound on planar graphs. When an input graph arrives with a sequence witnessing a small value, the authors obtain polynomial-time algorithms for Maximum Induced d-Regular Subgraph and Induced Disjoint Paths. The same boundedness assumption yields balanced separators dominated by a constant number of vertices and, in sparse graphs, forces bounded treewidth under bounded degree or strongly sublinear treewidth under biclique-freeness.

Core claim

Reduced component max-leaf, obtained by taking the maximum leaf count over spanning trees of components after a sequence of contractions, sits strictly between clique-width and reduced bandwidth. Graphs supplied with a witnessing contraction sequence of bounded reduced component max-leaf admit polynomial algorithms for Maximum Induced d-Regular Subgraph and Induced Disjoint Paths. In any sparse class of bounded reduced component max-leaf, bounded maximum degree implies bounded treewidth while the absence of a large biclique implies strongly sublinear treewidth; the former follows from the existence of balanced separators dominated by a bounded number of vertices. Most reduced parameters, the

What carries the argument

A contraction sequence witnessing bounded reduced component max-leaf, where component max-leaf is the largest number of leaves in any spanning tree of a connected component.

If this is right

  • Bounded degree together with bounded reduced component max-leaf forces bounded treewidth.
  • K_{t,t}-subgraph-free graphs with bounded reduced component max-leaf have strongly sublinear treewidth.
  • Graphs with bounded reduced component max-leaf possess balanced separators dominated by a bounded number of vertices.
  • The class of graphs with bounded reduced component max-leaf is closed under first-order transductions.
  • Three-dimensional grids have unbounded reduced bandwidth, so planar graphs cannot first-order transduce them.

Where Pith is reading between the lines

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

  • The separator property may extend algorithmic tractability to additional problems already known to be tractable on unit interval graphs.
  • The closure under transductions suggests that non-transducibility proofs for other grid-like structures could be obtained by showing unbounded reduced bandwidth on those structures.
  • The same contraction-sequence technique might unify tractability results for further intermediate parameters between clique-width and bandwidth.

Load-bearing premise

The input graphs are supplied together with an explicit contraction sequence that bounds the reduced component max-leaf value.

What would settle it

A single planar graph on which every contraction sequence has reduced component max-leaf growing with the size of the graph, or a graph with a bounded reduced component max-leaf sequence for which Induced Disjoint Paths cannot be solved in polynomial time.

Figures

Figures reproduced from arXiv: 2604.19138 by Colin Geniet, \'Edouard Bonnet, Julien Duron, O-joung Kwon, Yeonsu Chang.

Figure 1
Figure 1. Figure 1: Hasse diagram of the handled families of classes. The shaded families are those closed [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: A (7, 7)-wall. A linear ordering of a finite set S is a bijection ψ : S → [|S|]. For a graph G, a linear ordering of V (G) is also referred to as a linear ordering of G. 2.1 Contraction sequence and reduced-f A trigraph is a triple G = (V, E, R) where V is a finite set, and E and R are disjoint subsets of [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: A fully red component in Lemma 3.1. Lemma 3.1. For any weighted graph (G, w) with cml↓ (G) ⩽ k, there is a (1 − 1 2k+3 )-balanced separator S of (G, w) such that S is contained in the open neighborhood of at most k vertices of G. Proof. Fix a contraction sequence Pn, . . . ,P1 witnessing that cml↓ (G) = k. For each i ∈ [n], let Bi ⊆ Pi be the set of parts that have a black neighbor in G/Pi , and Ri = Pi \ … view at source ↗
Figure 4
Figure 4. Figure 4: The 7 × 7 Pohoata–Davies grid. Given a positive integer n, the n × n Pohoata–Davies grid [42, 19] is the graph obtained from the disjoint union of n paths on n vertices each, by adding for each i ∈ [n], a vertex adjacent to the i-th vertex of each path; see [PITH_FULL_IMAGE:figures/full_fig_p017_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: The partition P ′ is obtained from a partition P by merging P1 and P2 into P ∗ , and H is a connected red-induced subtrigraph of G/P ′ containing P ∗ . The trigraph F is the subtrigraph of G/P induced by (V (H) \ {P ∗}) ∪ {P1, P2}. Each part in Q1 ∪ Q2 is adjacent to one of P1 and P2 by a black edge, but become adjacent to P ∗ by a red edge. We first consider the case that {P1, P2} ⊆ O. As P \ {P1, P2} = P… view at source ↗
Figure 6
Figure 6. Figure 6: The partition P ′ is obtained from a partition P by merging P1 and P2 into P ∗ , and H is a connected red-induced subtrigraph of G/P ′ not containing P ∗ . It is possible that in G/P, P1 and P2 have no red edges to H, but P ∗ is adjacent to H by red edges in G/P ′ . • U contains at most α vertices from each part in O, • if O ∩ Qi ̸= ∅ for some i, then {Pi} ∪ Qi ⊆ O, |UQi | ⩽ α, and |U ∩ Q| ⩾ 1 for every Q … view at source ↗
Figure 7
Figure 7. Figure 7: We require that the restriction of each solution to an IDP separator consists of paths of [PITH_FULL_IMAGE:figures/full_fig_p037_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: The case where an IDP separator lies both outside and inside [PITH_FULL_IMAGE:figures/full_fig_p038_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: A (3, 4)-mixed grid that is a unit interval graph. v1,1 v1,2 v1,3 v1,4 v2,1 v2,2 v2,3 v2,4 v3,1 v3,2 v3,3 v3,4 [PITH_FULL_IMAGE:figures/full_fig_p044_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: A (3, 4)-mixed grid that is a clique-column grid. • Sufficiently long subdivisions of grids have bounded stretch-width [10]. • Clique-column grids have unbounded mim-width [35, Lemma 3.8]. • Mim-width, sim-width [35], and treewidth are equivalent on Kt,t-subgraph-free graphs [17]. Thus, Pohoata–Davies grids have unbounded mim-width and unbounded sim-width. • Interval graphs have unbounded cml↓ , as they h… view at source ↗
read the original abstract

Reduced parameters [BKW, JCTB '26; BKRT, SODA '22] are defined via contraction sequences. Based on this framework, we introduce the reduced component max-leaf, denoted by $\operatorname{cml}^\downarrow$, where component max-leaf is the maximum number of leaves in any spanning tree of any connected component. Reduced component max-leaf is strictly sandwiched between clique-width and reduced bandwidth, it is bounded in unit interval graphs, and unbounded in planar graphs. We design polynomial-time algorithms for problems such as \textsc{Maximum Induced $d$-Regular Subgraph} and \textsc{Induced Disjoint Paths} in graphs given with a contraction sequence witnessing low $\operatorname{cml}^\downarrow$, unifying and extending tractability results for classes of bounded clique-width and unit interval graphs. We get the following collapses in sparse classes of bounded $\operatorname{cml}^\downarrow$: bounded maximum degree implies bounded treewidth, whereas $K_{t,t}$-subgraph-freeness implies strongly sublinear treewidth; we show the latter, more generally, for classes of bounded reduced cutwidth. We establish the former result by showing that graphs with bounded $\operatorname{cml}^\downarrow$ admit balanced separators dominated by a bounded number of vertices. We then showcase an application of the reduced parameters to establishing non-transducibility results. We prove that for most reduced parameters $p^\downarrow$ (including reduced bandwidth), the family of classes of bounded $p^\downarrow$ is closed under first-order transductions. We then answer a question of [BKW '26] by showing that the 3-dimensional grids have unbounded reduced bandwidth. As the class of planar graphs (or any class of bounded genus) has bounded reduced bandwidth [BKW '26], this reproves a recent result [GPP, LICS '25] that planar graphs do not first-order transduce the 3-dimensional grids.

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.

Referee Report

0 major / 2 minor

Summary. The manuscript introduces the reduced component max-leaf parameter (cml↓) within the reduced-parameters framework based on contraction sequences. It establishes that cml↓ is strictly sandwiched between clique-width and reduced bandwidth, bounded on unit interval graphs, and unbounded on planar graphs. Polynomial-time algorithms are given for Maximum Induced d-Regular Subgraph and Induced Disjoint Paths (among others) when a witnessing contraction sequence of low cml↓ is provided as input. Structural results include a balanced-separator lemma implying that bounded cml↓ plus bounded degree yields bounded treewidth (and, more generally, K_{t,t}-freeness yields strongly sublinear treewidth, also shown for reduced cutwidth). The paper further proves that classes of bounded reduced parameters are closed under first-order transductions and applies this to show that 3-dimensional grids have unbounded reduced bandwidth, reproving that planar graphs do not FO-transduce 3D grids.

Significance. If the results hold, the work extends the reduced-parameters program with a new intermediate parameter that unifies tractability for clique-width and unit-interval graphs on induced-subgraph problems. The balanced-separator lemma and transducibility-closure results supply reusable tools for sparse classes and logical definability, while the 3D-grid application directly resolves a question from prior work on non-transducibility.

minor comments (2)
  1. In the algorithmic sections, the dependence on an explicit contraction sequence as input is clearly stated, but a short discussion of whether low cml↓ can be recognized in polynomial time (or is NP-hard) would strengthen the presentation of the results' applicability.
  2. The notation for component max-leaf and its reduced variant should be introduced with a self-contained definition before the sandwiching theorems to improve readability for readers unfamiliar with the prior reduced-parameters papers.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary, significance assessment, and recommendation of minor revision. The report accurately captures the main contributions of the paper. As no specific major comments were listed under the MAJOR COMMENTS section, we have no point-by-point responses to address. We will incorporate any minor editorial or polishing changes in the revised version.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper introduces the new parameter cml↓ by direct definition from the contraction-sequence framework of the cited prior works and then supplies independent proofs for its sandwiching between clique-width and reduced bandwidth, its boundedness on unit interval graphs, the balanced-separator lemma, the polynomial-time algorithms on explicit contraction sequences, and the FO-transduction closure for most reduced parameters. These steps rely on explicit constructions and lemmas rather than any equation or claim that reduces by construction to a fitted input, self-definition, or unverified self-citation chain. The 3D-grid unboundedness result is a fresh construction that answers an open question from the cited prior paper, and the reproof for planar graphs simply invokes an externally stated fact from that prior work. No load-bearing derivation collapses to its own inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The central claims rest on the new definition of cml↓ via contraction sequences and standard background from graph theory and prior reduced-parameter papers; no free parameters or invented entities beyond the parameter itself.

axioms (1)
  • standard math Standard definitions and properties of clique-width, bandwidth, contraction sequences, and first-order transductions from the cited literature [BKW, JCTB '26; BKRT, SODA '22; GPP, LICS '25].
    Invoked throughout to position the new parameter and derive algorithmic and structural consequences.
invented entities (1)
  • reduced component max-leaf (cml↓) no independent evidence
    purpose: New graph parameter measuring maximum leaves in spanning trees of components under contraction sequences.
    Newly introduced to sit between clique-width and reduced bandwidth and enable the stated algorithms and collapses.

pith-pipeline@v0.9.0 · 5671 in / 1454 out tokens · 38914 ms · 2026-05-10T02:05:34.910491+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

47 extracted references · 47 canonical work pages

  1. [1]

    On the tree-width of even-hole-free graphs.Eur

    Pierre Aboulker, Isolde Adler, Eun Jung Kim, Ni Luh Dewi Sintiari, and Nicolas Trotignon. On the tree-width of even-hole-free graphs.Eur. J. Comb., 98:103394, 2021

    work page 2021

  2. [2]

    Improved bounds for twin-width parameter variants with algorithmic applications to counting graph colorings.Theory Comput

    Ambroise Baril, Miguel Couceiro, and Victor Lagerkvist. Improved bounds for twin-width parameter variants with algorithmic applications to counting graph colorings.Theory Comput. Syst., 70(1):12, 2026

    work page 2026

  3. [3]

    Graph classes with structured neighborhoods and algorithmic applications.Theor

    R´ emy Belmonte and Martin Vatshelle. Graph classes with structured neighborhoods and algorithmic applications.Theor. Comput. Sci., 511:54–65, 2013. 48

    work page 2013

  4. [4]

    Deciding twin-width at most 4 is NP- complete

    Pierre Berg´ e,´Edouard Bonnet, and Hugues D´ epr´ es. Deciding twin-width at most 4 is NP- complete. InProc. ICALP 2022, volume 229 ofLIPIcs, pages 18:1–18:20. Schloss Dagstuhl, 2022

    work page 2022

  5. [5]

    Deciding twin-width at most 4 is NP- complete

    Pierre Berg´ e,´Edouard Bonnet, and Hugues D´ epr´ es. Deciding twin-width at most 4 is NP- complete. In49th EATCS International Conference on Automata, Languages, and Program- ming, volume 229 ofLIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 18, 20. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2022

    work page 2022

  6. [6]

    A logic-based algorithmic meta-theorem for mim-width

    Benjamin Bergougnoux, Jan Dreier, and Lars Jaffke. A logic-based algorithmic meta-theorem for mim-width. In Nikhil Bansal and Viswanath Nagarajan, editors,Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023, pages 3282–3304. SIAM, 2023

    work page 2023

  7. [7]

    More applications of thed-neighbor equivalence: acyclicity and connectivity constraints.SIAM J

    Benjamin Bergougnoux and Mamadou Moustapha Kant´ e. More applications of thed-neighbor equivalence: acyclicity and connectivity constraints.SIAM J. Discrete Math., 35(3):1881–1926, 2021

    work page 1926

  8. [8]

    Node multiway cut and subset feedback vertex set on graphs of bounded mim-width.Algorithmica, 84(5):1385–1417, 2022

    Benjamin Bergougnoux, Charis Papadopoulos, and Jan Arne Telle. Node multiway cut and subset feedback vertex set on graphs of bounded mim-width.Algorithmica, 84(5):1385–1417, 2022

    work page 2022

  9. [9]

    Low rank MSO.CoRR, abs/2502.08476, 2025

    Mikolaj Bojanczyk, Michal Pilipczuk, Wojciech Przybyszewski, Marek Sokolowski, and Gian- nos Stamoulis. Low rank MSO.CoRR, abs/2502.08476, 2025

    work page arXiv 2025

  10. [10]

    Stretch-width

    ´Edouard Bonnet and Julien Duron. Stretch-width. In Neeldhara Misra and Magnus Wahlstr¨ om, editors,18th International Symposium on Parameterized and Exact Computation, IPEC 2023, September 6-8, 2023, Amsterdam, The Netherlands, volume 285 ofLIPIcs, pages 8:1–8:15. Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Informatik, 2023

    work page 2023

  11. [11]

    Twin-width II: small classes.Comb

    ´Edouard Bonnet, Colin Geniet, Eun Jung Kim, St´ ephan Thomass´ e, and R´ emi Watrigant. Twin-width II: small classes.Comb. Theory, 2(2), 2022

    work page 2022

  12. [12]

    Twin-width III: max independent set, min dominating set, and coloring.SIAM J

    ´Edouard Bonnet, Colin Geniet, Eun Jung Kim, St´ ephan Thomass´ e, and R´ emi Watrigant. Twin-width III: max independent set, min dominating set, and coloring.SIAM J. Comput., 53(5):1602–1640, 2024

    work page 2024

  13. [13]

    Twin-width VI: the lens of contraction sequences

    ´Edouard Bonnet, Eun Jung Kim, Amadeus Reinald, and St´ ephan Thomass´ e. Twin-width VI: the lens of contraction sequences. In Joseph (Seffi) Naor and Niv Buchbinder, editors, Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, USA, January 9 - 12, 2022, pages 1036–1056. SIAM, 2022

    work page 2022

  14. [14]

    Twin-width I: tractable FO model checking.J

    ´Edouard Bonnet, Eun Jung Kim, St´ ephan Thomass´ e, and R´ emi Watrigant. Twin-width I: tractable FO model checking.J. ACM, 69(1):3:1–3:46, 2022

    work page 2022

  15. [15]

    ´Edouard Bonnet, O-joung Kwon, and David R. Wood. Reduced bandwidth: a qualitative strengthening of twin-width in minor-closed classes (and beyond).J. Combin. Theory Ser. B, 178:27–66, 2026

    work page 2026

  16. [16]

    Bound- ing the mim-width of hereditary graph classes.J

    Nick Brettell, Jake Horsfield, Andrea Munaro, Giacomo Paesani, and Dani¨ el Paulusma. Bound- ing the mim-width of hereditary graph classes.J. Graph Theory, 99(1):117–151, 2022. 49

    work page 2022

  17. [17]

    Comparing width pa- rameters on graph classes.European J

    Nick Brettell, Andrea Munaro, Dani¨ el Paulusma, and Shizhou Yang. Comparing width pa- rameters on graph classes.European J. Combin., 127:Paper No. 104163, 30, 2025

    work page 2025

  18. [18]

    Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems.Theoret

    Binh-Minh Bui-Xuan, Jan Arne Telle, and Martin Vatshelle. Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems.Theoret. Comput. Sci., 511:66–76, 2013

    work page 2013

  19. [19]

    Induced subgraphs and tree decompositions

    Maria Chudnovsky. Induced subgraphs and tree decompositions. In Jim Geelen, Daniel Kr´ al, and Alexander Scott, editors,Oberwolfach report 1/2022, 2022

    work page 2022

  20. [20]

    Makowsky, and Udi Rotics

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

    work page 2000

  21. [21]

    A note on the np-hardness of two matching problems in induced subgrids.Discret

    Marc Demange and T´ ınaz Ekim. A note on the np-hardness of two matching problems in induced subgrids.Discret. Math. Theor. Comput. Sci., 15(2):233–242, 2013

    work page 2013

  22. [22]

    Indiscernibles and flatness in monadically stable and monadically NIP classes

    Jan Dreier, Nikolas M¨ ahlmann, Sebastian Siebertz, and Szymon Toru´ nczyk. Indiscernibles and flatness in monadically stable and monadically NIP classes. In50th International Colloquium on Automata, Languages, and Programming (ICALP 2023), volume 261, pages 125:1–125:18, 2023

    work page 2023

  23. [23]

    On classes of graphs with strongly sublinear separators.European J

    Zdenˇ ek Dvoˇ r´ ak. On classes of graphs with strongly sublinear separators.European J. Combin., 71:1–11, 2018

    work page 2018

  24. [24]

    Strongly sublinear separators and polynomial expansion

    Zdenˇ ek Dvoˇ r´ ak and Sergey Norin. Strongly sublinear separators and polynomial expansion. SIAM J. Discret. Math., 30(2):1095–1101, 2016

    work page 2016

  25. [25]

    Treewidth of graphs with balanced separations.J

    Zdenˇ ek Dvoˇ r´ ak and Sergey Norin. Treewidth of graphs with balanced separations.J. Comb. Theory B, 137:137–144, 2019

    work page 2019

  26. [26]

    Fomin, Petr A

    Fedor V. Fomin, Petr A. Golovach, Ignasi Sau, Giannos Stamoulis, and Dimitrios M. Thilikos. Compound logics for modification problems.ACM Trans. Comput. Log., 26(1):2:1–2:57, 2025

    work page 2025

  27. [27]

    On local and non-local properties

    Haim Gaifman. On local and non-local properties. In J. Stern, editor,Proceedings of the Herbrand Symposium, volume 107 ofStudies in Logic and the Foundations of Mathematics, pages 105–135. Elsevier, 1982

    work page 1982

  28. [28]

    3D-grids are not transducible from planar graphs

    Jakub Gajarsk´ y, Michal Pilipczuk, and Filip Pokr´ yvka. 3D-grids are not transducible from planar graphs. In40th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2025, Singapore, June 23-26, 2025, pages 831–842. IEEE, 2025

    work page 2025

  29. [29]

    Quasi-polynomial time techniques for independent set and beyond in heredi- tary graph classes.PhD University of California Santa Barbara, 2023

    Peter Gartland. Quasi-polynomial time techniques for independent set and beyond in heredi- tary graph classes.PhD University of California Santa Barbara, 2023

    work page 2023

  30. [30]

    The tree-width of clique-width bounded graphs withoutKn, n

    Frank Gurski and Egon Wanke. The tree-width of clique-width bounded graphs withoutKn, n . In Ulrik Brandes and Dorothea Wagner, editors,Graph-Theoretic Concepts in Computer Sci- ence, 26th International Workshop, WG 2000, Konstanz, Germany, June 15-17, 2000, Pro- ceedings, volume 1928 ofLecture Notes in Computer Science, pages 196–205. Springer, 2000

    work page 2000

  31. [31]

    Twin-width of planar graphs is at most 8, and some related bounds.SIAM J

    Petr Hlinen´ y and Jan Jedelsk´ y. Twin-width of planar graphs is at most 8, and some related bounds.SIAM J. Discret. Math., 39(4):2003–2048, 2025. 50

    work page 2003

  32. [32]

    Expander graphs and their applications

    Shlomo Hoory, Nathan Linial, and Avi Wigderson. Expander graphs and their applications. Bulletin of the American Mathematical Society, 43(4):439–561, 2006

    work page 2006

  33. [33]

    Mim-Width I

    Lars Jaffke, O-joung Kwon, and Jan Arne Telle. Mim-Width I. Induced path problems.Discrete Appl. Math., 278:153–168, 2020

    work page 2020

  34. [34]

    Mim-width II

    Lars Jaffke, O-joung Kwon, and Jan Arne Telle. Mim-width II. The feedback vertex set problem.Algorithmica, 82(1):118–145, 2020

    work page 2020

  35. [35]

    Dong Yeap Kang, O-joung Kwon, Torstein J. F. Strømme, and Jan Arne Telle. A width parameter useful for chordal and co-comparability graphs.Theoret. Comput. Sci., 704:1–17, 2017

    work page 2017

  36. [36]

    An inequality related to the isoperimetric inequal- ity.Bulletin of the American Mathematical Society, 55:961–962, 1949

    Lynn Harold Loomis and Hassler Whitney. An inequality related to the isoperimetric inequal- ity.Bulletin of the American Mathematical Society, 55:961–962, 1949

    work page 1949

  37. [37]

    Sridhar Natarajan and Alan P. Sprague. Disjoint paths in circular arc graphs.Nordic J. Comput., 3(3):256–270, 1996

    work page 1996

  38. [38]

    Springer Publishing Company, Incorporated, 2012

    Jaroslav Neˇ setˇ ril and Patrice Ossona de Mendez.Sparsity: Graphs, Structures, and Algorithms. Springer Publishing Company, Incorporated, 2012

    work page 2012

  39. [39]

    Problems parameterized by treewidth tractable in single exponential time: A logical approach

    Michal Pilipczuk. Problems parameterized by treewidth tractable in single exponential time: A logical approach. In Filip Murlak and Piotr Sankowski, editors,Mathematical Foundations of Computer Science 2011 - 36th International Symposium, MFCS 2011, Warsaw, Poland, August 22-26, 2011. Proceedings, volume 6907 ofLecture Notes in Computer Science, pages 520...

    work page 2011

  40. [40]

    Algorithms and data structures for first-order logic with connectivity under vertex failures

    Michal Pilipczuk, Nicole Schirrmacher, Sebastian Siebertz, Szymon Torunczyk, and Alexan- dre Vigny. Algorithms and data structures for first-order logic with connectivity under vertex failures. In Mikolaj Bojanczyk, Emanuela Merelli, and David P. Woodruff, editors,49th Inter- national Colloquium on Automata, Languages, and Programming, ICALP 2022, Paris, ...

    work page 2022

  41. [41]

    Serge Plotkin, Satish Rao, and Warren D. Smith. Shallow excluded minors and improved graph decompositions. InProceedings of the Fifth Annual ACM-SIAM Symposium on Dis- crete Algorithms, SODA ’94, page 462–470, USA, 1994. Society for Industrial and Applied Mathematics

    work page 1994

  42. [42]

    Unavoidable induced subgraphs of large graphs

    Cosmin Pohoata. Unavoidable induced subgraphs of large graphs. Senior thesis, Department of Mathematics, Princeton University, 2014

    work page 2014

  43. [43]

    Graph Minors

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

    work page 1986

  44. [44]

    Thilikos, and Alexandre Vigny

    Nicole Schirrmacher, Sebastian Siebertz, Giannos Stamoulis, Dimitrios M. Thilikos, and Alexandre Vigny. Model checking disjoint-paths logic on topological-minor-free graph classes. In Pawel Sobocinski, Ugo Dal Lago, and Javier Esparza, editors,Proceedings of the 39th An- nual ACM/IEEE Symposium on Logic in Computer Science, LICS 2024, Tallinn, Estonia, Ju...

    work page 2024

  45. [45]

    Algorithms for vertex partitioning problems on partialk-trees.SIAM J

    Jan Arne Telle and Andrzej Proskurowski. Algorithms for vertex partitioning problems on partialk-trees.SIAM J. Discrete Math., 10(4):529–550, 1997

    work page 1997

  46. [46]

    PhD thesis, Univ

    Martin Vatshelle.New Width Parameters of Graphs. PhD thesis, Univ. Bergen, 2012

    work page 2012

  47. [47]

    Geometric and combinatorial structures on graphs.PhD thesis, Technical University of Berlin, Dec 2007

    Florian Zickfeld. Geometric and combinatorial structures on graphs.PhD thesis, Technical University of Berlin, Dec 2007. 52

    work page 2007