Pith. sign in

REVIEW 2 major objections 4 minor 44 references

Unavoidable butterfly minors in digraphs of large cycle rank

T0 review · 2 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash

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

Pith's one-line read Every digraph whose cycle rank is large enough contains one of three explicit digraphs—a directed ladder, a directed cycle chain, or a directed tree chain—as a butterfly minor, and this yields an exact characterization of…

desk verdict Important result with a real-looking gap in Lemma 7.17: the bridge from clean to spotless decompositions may not hold as written. read the letter →

arxiv 2507.11814 v1 pith:D2VC6R3M submitted 2025-07-16 math.CO cs.DM

Meike Hatzel , O-joung Kwon , Myounghwan Lee , Sebastian Wiederrecht This is my paper
classification math.COcs.DM MSC 05C2005C83
keywords cyclerankbutterflyminorsdirectedtreewidthgridtheoremweakcoloringnumbersladderstreechainstreedepth
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

Cycle rank is a depth measure for digraphs that dates back to 1963 and behaves like the digraph analogue of treedepth: acyclic digraphs have rank zero, strongly connected pieces contribute one more than the best vertex deletion, and components combine by taking the maximum. The paper proves that this parameter is governed by exactly three simple obstruction families: if a digraph's cycle rank is at least $f(k)$, then it must contain a directed ladder $L_k$, a directed cycle chain $CC_k$, or a directed tree chain $TC_k$ as a butterfly minor, where butterfly minor is the directed contraction operation that only identifies edges with a unique tail or a unique head. This is Theorem 1.1, and it implies Theorem 1.2: a class of digraphs closed under butterfly minors has bounded cycle rank if and only if it excludes all three families for some fixed $k$. The paper also proves an exact identity connecting cycle rank to a directed version of weak coloring numbers: the cycle rank equals the weak $(\infty,\to)$-coloring number minus one. The broader significance is that explicit unavoidable structures for digraph width parameters are rare, and a theorem of this kind turns high cycle rank into a substructure one can point to and certify.

What carries the argument

The proof centers on chain decompositions of digraphs: a rooted binary tree whose root is the whole digraph, whose leaves are strongly connected digraphs, and in which every internal node's digraph is formed from its two children by a mixed link. A mixed link joins two 2-terminal strongly connected digraphs by a mixed chain, a sequence of relaxed ladders and paths that interpolates between a relaxed chain and a relaxed ladder; the weight of a mixed chain is its length plus the orders of its relaxed ladders. The decomposition is refined through two structural properties, called clean and spotless, and a spotless chain decomposition of height $k+3$ yields a relaxed tree chain of order $k$ as a butterfly minor. High directed treewidth is handled separately by the directed grid theorem: a digraph of large directed treewidth contains a large cylindrical grid, from which a cycle chain, and in order $2k$ a ladder, is extracted as a butterfly minor. The identity $\mathrm{cr}(G)=\mathrm{wcol}^{\to}_{\infty}(G)-1$ is proved by an induction that moves between cycle-rank decompositions and linear vertex orderings.

What would settle it

Exhibit, for some fixed $k$, a sequence of digraphs whose cycle rank is unbounded but none of which contains $L_k$, $CC_k$, or $TC_k$ as a butterfly minor. This would directly contradict Theorem 1.1. A less direct check is to construct a digraph with large directed treewidth but no large cylindrical grid butterfly minor, which would invalidate the proof's main reduction step.

Watch

Extended reading notes

Core claim

The central claim, on the paper's own terms, is Theorem 1.1: there is a function $f_{1.1}:\mathbb{N}\to\mathbb{N}$ such that for every positive integer $k$, every digraph of cycle rank at least $f_{1.1}(k)$ contains $L_k$, $CC_k$, or $TC_k$ as a butterfly minor. Here $L_k$ is a directed ladder (two directed paths of length $k$ joined by antiparallel rungs), $CC_k$ is a directed cycle chain (a path whose edges are replaced by 2-cycles), and $TC_k$ is a directed tree chain (built recursively from two copies of $TC_{k-1}$ linked by two crossing edges). A butterfly minor is obtained by deleting vertices and edges and by contracting only edges whose tail or head is unique. The paper establishes that each of the three families has unbounded cycle rank, that ladders and cycle chains appear inside large cylindrical grids, that tree chains do not, and that the three families are pairwise independent, so none is redundant. Theorem 1.2 follows: a butterfly-minor-closed class of digraphs has bounded cycle rank if and only if there is some $k$ such that it contains none of $L_k$, $CC_k$, $TC_k$. A separate theorem, Theorem 1.3, states the exact identity $\mathrm{cr}(G)=\mathrm{wcol}^{\to}_{\infty}(G)-1$ between cycle rank and the directed weak coloring number.

Load-bearing premise

The proof leans on the directed grid theorem, which says that every digraph of sufficiently large directed treewidth contains a large cylindrical grid as a butterfly minor; if that theorem, or the concrete bound used for it, failed, the reduction from high cycle rank to bounded directed treewidth would collapse.

Editorial extensions

If this is right

  • For every butterfly-minor-closed class of digraphs, bounded cycle rank is equivalent to excluding all of $L_k$, $CC_k$, $TC_k$ for some fixed $k$.
  • Large cylindrical grids already force cycle chains, and order-$2k$ grids force ladders, so the only genuinely new obstruction supplied beyond the directed grid theorem is the tree chain, which is not a butterfly minor of any cylindrical grid.
  • The three obstruction families are pairwise independent: no family lies in the butterfly-minor closure of another, so all three are needed in Theorem 1.1.
  • Any digraph containing one of the three order-$k$ structures has cycle rank at least $\lfloor\log k\rfloor$ for ladders and cycle chains, or at least $k$ for tree chains, and butterfly minors cannot raise cycle rank.
  • Cycle rank equals the weak $(\infty,\to)$-coloring number minus one, giving an ordering-based description that mirrors the classical treedepth/weak-coloring relationship for undirected graphs.

Reading between the lines

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

  • The proof is described as mostly constructive; if the remaining Erdős–Pósa step can be made fully algorithmic, the obstruction theorem would point toward a parameterized algorithm or approximation for cycle rank, a question the paper explicitly leaves open.
  • The equality with the weak $(\infty,\to)$-coloring number suggests that cycle rank can be understood through vertex orderings and directed reachability, potentially connecting it to directed notions of sparsity and bounded expansion.
  • The tower-type bound in $f_{1.1}$ is largely inherited from the directed grid theorem; the planar analogue already yields a double-exponential bound, so a grid-free proof of the same structural theorem would likely give a substantially smaller, and more usable, function.
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

2 major / 4 minor

Summary. The paper proves an unavoidable-minors theorem for cycle rank in digraphs: there is a function f such that every digraph with cycle rank at least f(k) contains a directed ladder L_k, a directed cycle chain CC_k, or a directed tree chain TC_k as a butterfly minor. From this it derives a characterization of butterfly-minor-closed classes of bounded cycle rank, and it proves a new relation equating cycle rank with the weak (∞,→)-coloring number minus one. The proof combines the directed grid theorem with an Erdős–Pósa argument, introduces chain decompositions and auxiliary notions of clean and spotless decompositions, and then extracts one of the three obstructions. The paper also proves pairwise independence of the three obstruction families.

Significance. If the main theorem is correct, it resolves a natural open problem in the area of digraph width parameters. The obstruction families are simple and explicit, and the resulting characterization of butterfly-minor-closed classes of bounded cycle rank is a strong structural statement. The proof is long but mostly self-contained, and it includes a direct proof of monotonicity of cycle rank under butterfly minors and a short, clean proof of the weak-coloring-number characterization in Section 9. The main result is conditional on the directed grid theorem, which is a standard external dependency rather than a circularity. However, the iterative refinement argument in Section 7 contains two load-bearing gaps, described below, so the significance is conditional on those gaps being repaired.

major comments (2)
  1. [§7, Lemma 7.17] The proof of Lemma 7.17 applies Lemma 7.6 and then refers to the resulting decomposition T'' as a clean chain decomposition satisfying one of the three outcomes. This is not what Lemma 7.6 states: only outcomes (1) and (3) assert cleanliness, while outcome (2) is stated only for a chain decomposition. The proof of outcome (2) goes through Lemma 7.4, whose statement and proof do not establish that the clean property is preserved under the tree modification. Since the minimality condition in Lemma 7.17 is over clean chain decompositions, the contradiction producing a smaller i1 requires T'' to be clean, and this is not supplied. This gap is load-bearing for the extraction of a spotless decomposition and hence for the proof of Theorem 1.1.
  2. [§7, Lemmas 7.16 and 7.17] Both Lemma 7.16 and Lemma 7.17 use the inference that v(T'')[1,z] >lex v(T')[1,z] implies ||v(T'')[1,z]||_1 > ||v(T')[1,z]||_1. Lexicographic order does not compare ℓ1-norms; for example, (2,0,0) is lexicographically larger than (1,1,1) while having a smaller ℓ1-norm. The subsequent conclusions that the width of T'' is at least 4t^2+t−1 and that there exists i1 < i with the required norm equality both depend on this norm inequality. As written, the minimality argument in both lemmas is therefore incomplete.
minor comments (4)
  1. [§1, Theorem 1.1 display] The displayed formula for f1.1(k) is typeset ambiguously; the tower of exponents should be parenthesized so that the expression matches the recurrence in Theorem 7.18.
  2. [§2, Lemma 2.2] In the proof of Lemma 2.2, the text refers to P' shortly after defining P* and Q*; this appears to be a typo for P*, and the notation should be made consistent.
  3. [§9, Observation 9.1] The wording of Observation 9.1 is confusing about the direction of reachability: the definitions say w is weakly reachable from v, but the observation says 'v is strongly reachable from w'. Please align the notation with the definitions.
  4. [§4, Lemma 4.1] The phrase 'the edges on P between the endpoints of Y4i−3 and X4i−1 are butterfly contractible' is terse; since P and Q have opposite orientations, it would help to state explicitly which endpoint of each rung is used in the contraction order.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the main theorem is derived from the external directed grid theorem and self-contained structural lemmas, with no fitted inputs or predictions that reduce to their own assumptions.

full rationale

The derivation chain in this paper is self-contained apart from standard external theorems. Theorem 1.1 is proved by combining the directed grid theorem of Kawarabayashi and Kreutzer (Theorem 2.6), an Erdős-Pósa type argument for digraphs of bounded directed treewidth (Lemma 7.1), and a sequence of structural refinements of chain decompositions (Lemmas 7.5, 7.6, 7.14, 7.16, 7.17). No parameter is fitted to the target conclusion, and no 'prediction' is equated with an input by construction. The improved bound from [18] is used only to state the numerical form of f_{1.1}; the correctness of Theorem 1.1 does not depend on that specific bound being the best possible, so this is not a load-bearing self-citation. The cited Lemma 2.1 from [19] is a technical path-untangling tool with an independent proof in the cited work, not an assumption that smuggles in the main result. Theorem 1.3, identifying cycle rank with the weak (∞,→)-coloring number minus one, is proved directly by induction on the two parameters in Lemma 9.2 and is not a definitional renaming. The alleged issue with Lemma 7.17 concerns whether a cleanliness property is preserved in a minimality argument; that is a proof-correctness concern, not a circularity concern, because it does not make the theorem's conclusion identical to its hypotheses. Overall, the central claims have independent mathematical content and are not forced by self-citation or by definition.

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

No free parameters are fitted; the functions f in the paper are constructed, not tuned. The only unproved inputs are three published theorems from the literature, none written by the present authors, so there is no circularity.

assumptions (3)
  • standard math Directed grid theorem (Kawarabayashi-Kreutzer)
    Used in Theorem 7.2 to conclude that a digraph of directed treewidth at least f_dtw(t-1) contains a cylindrical grid of order t-1, hence a CC_t butterfly minor. Cited as Theorem 2.6, not proved.
  • standard math Improved bound on f_dtw (Hatzel et al. 2024)
    Used to state the explicit double-exponential bound in Theorem 1.1. Cited as [18].
  • standard math Characterization of butterfly minors of cylindrical grids (Bensmail et al. 2023)
    Used only in Lemma 8.7 to show TC_k is not a butterfly minor of a cylindrical grid; this is part of the pairwise independence section, not the main theorem.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Unavoidable butterfly minors in digraphs of large cycle rank." pith.science (2026). https://pith.science/paper/D2VC6R3M

@misc{pith2026250711814,
  author       = {Pith},
  title        = {Pith review of: Unavoidable butterfly minors in digraphs of large cycle rank},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/D2VC6R3M}},
  note         = {Machine review of arXiv:2507.11814}
}
abstract

Cycle rank is one of the depth parameters for digraphs introduced by Eggan in 1963. We show that there exists a function $f:\mathbb{N}\to \mathbb{N}$ such that every digraph of cycle rank at least $f(k)$ contains a directed cycle chain, a directed ladder, or a directed tree chain of order $k$ as a butterfly minor. We also investigate a new connection between cycle rank and a directed analogue of the weak coloring number of graphs.

Figures

Figures reproduced from arXiv: 2507.11814 by the authors.

Figure 1
Figure 1. The directed ladder L4 of order 4, the directed cycle chain CC4 of order 4, and the directed tree chain TC3 of order 3. cycle rank at GROW 2022. Note that the cycle rank of a digraph does not increase when taking a butterfly minor, see Lemma 2.5. Our main result is providing three obstruction families for cycle rank in terms of butterfly minors. Characterizing a graph width parameter in terms of such obstructions, t… view at source ↗
Figure 2
Figure 2. The hierarchy of the mentioned digraph classes. We [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 3
Figure 3. An example of laced paths P and Q. • z1P w1, z2P w2, . . . , znP wn appear in this order along P, and • znP wn, zn−1P wn−1, . . . , z1P w1 appear in this order along Q. See [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗
Figures from the paper (16 more)
Figure 4
Figure 4. Figure 4: The cylindrical grid of order 4 The cylindrical grid of order k is the digraph obtained from the disjoint union of k directed cycles v i 1 v i 2 . . . vi 2k−1 v i 2k v i 1 , i ∈ [k], by adding the path v 1 j v 2 j . . . vk−1 j v k j for every odd j ∈ [2k] and the path …
Figure 5
Figure 5. Figure 5: To obtain a cycle chain as a butterfly minor, we first t [PITH_FULL_IMAGE:figures/full_fig_p013_5.png]
Figure 6
Figure 6. Figure 6: Notice that each Ri in a relaxed chain might be of length 0. In both constructions, it is possible that the left endpoints are the same, and the right endpoints are the same. Relaxed ladders. Let p, q, p′ , q′ be vertices of a digraph G such that {p, q} ∩ {p ′ , q′} = …
Figure 7
Figure 7. Figure 7: An example of a mixed chain of length k. It is possible that the left endpoints are the same, and the right endpoints are the same. • for each odd i ∈ [k + 1], Hi is a relaxed ladder where (pi−1, qi−1) is the pair of left endpoints and (pi , qi) is the pair of right en…
Figure 8
Figure 8. Figure 8: The subdigraph Inext(Q1) is depicted by dashed lines. Let H be a mixed chain with the tuple (Hi : i ∈ [x + 1]),(Ri : i ∈ [x]) and for each i ∈ [k + 1], let (Pi , Qi) be the pair of boundary-paths of Hi . For the first and last relaxed ladders H1 and Hx+1, it is conven…
Figure 9
Figure 9. Figure 9: The recursive construction of a digraph in [PITH_FULL_IMAGE:figures/full_fig_p020_9.png]
Figure 10
Figure 10. Figure 10: Illustrations of Case 1 and Case 2 in Lemma 4.6. are two copies of (TCk−1, s, t). Observe that (G2k−1, x, y) is constructed from the disjoint union of four 2-terminal digraphs (H1, x1, y1), (H2, x2, y2), (H3, x3, y3), (H4, x4, y4) in T C2k−3 as follows: For each i ∈ […
Figure 11
Figure 11. Figure 11: An illustration of directed paths A and B in Subcase 3.1 in Lemma 5.1. Every vertex of V (A) \ {x} has in-degree 1 in H, but there is a vertex of V (B) \ {y} of out-degree at least 2 in H, a tail of a (V (Zin), V (Zout))-path in some rung of Hk+1. This path is a (B, Q…
Figure 12
Figure 12. Figure 12: An example of a crossing pair (x, y). For a digraph G, a tuple T = (T, r, λ, η) is a chain decomposition of G if the following is satisfied: • (T, r) is a rooted tree and λ(r) = G, 27 [PITH_FULL_IMAGE:figures/full_fig_p027_12.png]
Figure 13
Figure 13. Figure 13: The positions of d, b, dα, bβ in the given chain decomposition in Lemma 7.4. Let P be a shortest (G1, G2)-path and let Q be a shortest (G2, G1)-path in G. Such paths exist because G is strongly connected. By Lemma 2.1 we may assume that P and Q are laced, and by Lemma…
Figure 14
Figure 14. Figure 14: The positions of x and y in Case 1 in Lemma 7.6. Both x and y are right with respect to cm. See [PITH_FULL_IMAGE:figures/full_fig_p036_14.png]
Figure 15
Figure 15. Figure 15: The positions of x, y, u in Subcase 2.1 in Lemma 7.6. Both x and u are left with respect to cm. is crossing with respect to d3. Let s = out-vertex(d2, d3). See [PITH_FULL_IMAGE:figures/full_fig_p037_15.png]
Figure 16
Figure 16. Figure 16: The positions of y, s in Subcase 2.2 in Lemma 7.6. The pair (s, y) is crossing with respect to d3. Subcase 2.3: Now, we assume that in-vertex(d2, d3) = ⊥. As in-vertex(cm−1, cm) 6= ⊥, d2 6= cm−1 and m ≥ 4. By Claim 7.7, in-vertex(d2, cm−1) 6= ⊥ and if α(m − 1) = 1, th…
Figure 17
Figure 17. Figure 17: The positions of x, w, u in Subcase 2.3 in Lemma 7.6. The vertex w is right with respect to cm and u is contained in in-arbor(cm). The case when α(m − 1) = 2 would be symmetric. Let u = in-vertex(d2, cm−1) and let w = in-vertex(cm−1, cm). See [PITH_FULL_IMAGE:figures…
Figure 18
Figure 18. Figure 18: A vertex labelling of TC3 and the digraph L′ 3 in the proof of Lemma 8.5. Lemma 8.5. Let k ≥ 3 and n ≥ 3 be integers. (1) TCk is not a butterfly minor of Ln. (2) Ln is not a butterfly minor of TCk. Proof. (1) We claim that TC3 is not a butterfly minor of Ln. Suppose i…
Figure 19
Figure 19. Figure 19: The black digraph is a plane embedding of the digra [PITH_FULL_IMAGE:figures/full_fig_p047_19.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

44 extracted references · 43 canonical work pages

  1. [1]

    Graph searching games and width measures for directed graphs

    Saeed Akhoondian Amiri, /suppress Lukasz Kaiser, Stephan Kreutzer, Roman Rabinovich, and Sebastian Siebertz. Graph searching games and width measures for directed graphs. In 32nd International Symposium on Theoretical Aspects of Computer Science , volume 30 of LIPIcs. Leibniz Int. Proc. Inform., pages 34–47. Schloss Dagstuhl. Leibniz-Zent. Inform., Wa dern, 2015

    work page 2015

  2. [2]

    The Erdos-Posa Property for Directed Graphs

    Saeed Akhoondian Amiri, Ken-Ichi Kawarabayashi, Steph an Kreutzer, and Paul Wollan. The Erd˝ os-P´ osa property for directed graphs, 2016. arXiv:1603.02504

    work page Pith review arXiv 2016

  3. [3]

    Decid- ing the Erd˝ os-P´ osa property in 3-connected digraphs

    Julien Bensmail, Victor Campos, Ana Karolinna Maia, Nic olas Nisse, and Ana Silva. Decid- ing the Erd˝ os-P´ osa property in 3-connected digraphs. InInternational Workshop on Graph- Theoretic Concepts in Computer Science , pages 59–71. Springer, 2023

    work page 2023

  4. [4]

    The dag-width of directed graphs

    Dietmar Berwanger, Anuj Dawar, Paul Hunter, Stephan Kre utzer, and Jan Obdrˇ z´ alek. The dag-width of directed graphs. Journal of Combinatorial Theory, Series B , 102(4):900–923, 2012

    work page 2012

  5. [5]

    Quickly excluding a forest

    Dan Bienstock, Neil Robertson, Paul Seymour, and Robin Thomas. Quickly excluding a forest. J. Combin. Theory Ser. B , 52(2):274–283, 1991

    work page 1991

  6. [6]

    Bodlaender, Jitender S

    Hans L. Bodlaender, Jitender S. Deogun, Klaus Jansen, To n Kloks, Dieter Kratsch, Heiko M¨ uller, and Zsolt Tuza. Rankings of graphs.SIAM J. Discrete Math. , 11(1):168–181, 1998

    work page 1998

  7. [7]

    Cabello, M

    S. Cabello, M. Krnc, and M. Milaniˇ c. 10th Workshop on Graph Classes, Optimization, and Width Parameters: GROW 2022 : Book of Open Problems : 19–22 Se ptember 2022, Koper, Slovenia. publisher M. Krnc, 2022

    work page 2022

  8. [8]

    Towards tight(er) bounds fo r the excluded grid theorem

    Julia Chuzhoy and Zihan Tan. Towards tight(er) bounds fo r the excluded grid theorem. J. Combin. Theory Ser. B , 146:219–265, 2021

    work page 2021

Show all 44 references
  1. [9]

    J. S. Deogun, T. Kloks, D. Kratsch, and H. M¨ uller. On vert ex ranking for permutation and other graphs. In STACS 94. 11th annual symposium on theoretical aspects of co mputer science, Caen, France, February 24–26, 1994. Proceedings , pages 747–758. Berlin: Springer, 1994

    1994

  2. [10]

    L. C. Eggan. Transition graphs and the star-height of re gular events. Michigan Math. J. , 10:385–397, 1963

    1963

  3. [11]

    Directed path-decompositions

    Joshua Erde. Directed path-decompositions. SIAM J. Discrete Math. , 34(1):415–430, 2020

    2020

  4. [12]

    Digraph width measures in parameterized algor ithmics

    Robert Ganian, Petr Hlinˇ en´ y, Joachim Kneis, Alexander Langer, Jan Obdrˇ z´ alek, and Peter Rossmanith. Digraph width measures in parameterized algor ithmics. Discrete Appl. Math. , 168:88–107, 2014

    2014

  5. [13]

    The grid theorem for vertex- minors

    Jim Geelen, O-joung Kwon, Rose McCarty, and Paul Wollan . The grid theorem for vertex- minors. J. Combin. Theory Ser. B , 158:93–116, 2023

    2023

  6. [14]

    Succinctness of regular expressions wi th interleaving, intersection and count- ing

    Wouter Gelade. Succinctness of regular expressions wi th interleaving, intersection and count- ing. Theoretical Computer Science, 411(31):2987–2998, 2010. 51

    2010

  7. [15]

    Giannopoulou, Paul Hunter, and Dimitrios M

    Archontia C. Giannopoulou, Paul Hunter, and Dimitrios M. Thilikos. Lifo-search: A min–max theorem and a searching game for cycle-rank and tree-depth. Discrete Applied Mathematics , 160(15):2089–2097, 2012

    2012

  8. [16]

    Digraph complexity measures and appli cations in formal language theory

    Hermann Gruber. Digraph complexity measures and appli cations in formal language theory. Discrete Math. Theor. Comput. Sci. , 14(2):189–204, 2012

    2012

  9. [17]

    Polynomial planar directed grid theorem

    Meike Hatzel, Ken-ichi Kawarabayashi, and Stephan Kre utzer. Polynomial planar directed grid theorem. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on D iscrete Algorithms, pages 1465–1484. SIAM, Philadelphia, PA, 2019

    2019

  10. [18]

    Cycles of Well- Linked Sets and an Elementary Bound for the Directed Grid The orem

    Meike Hatzel, Stephan Kreutzer, Marcelo Garlet Milani , and Irene Muzi. Cycles of Well- Linked Sets and an Elementary Bound for the Directed Grid The orem. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS) , pages 1–20, Los Alamitos, CA, USA, October...

    2024

  11. [19]

    Generating strongly 2-connect ed digraphs

    Meike Hatzel, Stephan Kreutzer, Evangelos Protopapas , Florian Reich, Giannos Stamoulis, and Sebastian Wiederrecht. Generating strongly 2-connect ed digraphs. arXiv preprint arXiv:2411.09791, 2024

    2024 arXiv

  12. [20]

    Digraph measures: Ke lly decompositions, games, and orderings

    Paul Hunter and Stephan Kreutzer. Digraph measures: Ke lly decompositions, games, and orderings. Theoretical Computer Science, 399(3):206–219, 2008

    2008

  13. [21]

    Thor Johnson, Neil Robertson, P. D. Seymour, and Robin T homas. Directed tree-width. J. Combin. Theory Ser. B , 82(1):138–154, 2001

    2001

  14. [22]

    The dire cted grid theorem

    Ken-ichi Kawarabayashi and Stephan Kreutzer. The dire cted grid theorem. In Proceedings of the forty-seventh annual ACM symposium on Theory of Computi ng, pages 655–664, 2015

    2015

  15. [23]

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

    2003

  16. [24]

    Digraphs of bounded width

    Stephan Kreutzer and O-joung Kwon. Digraphs of bounded width. In Jørgen Bang-Jensen and Gregory Gutin, editors, Classes of Directed Graphs , pages 405–466, Cham, 2018. Springer International Publishing

    2018

  17. [25]

    Algorithmic properties of sparse digraphs

    Stephan Kreutzer, Irene Muzi, Patrice Ossona de Mendez , Roman Rabinovich, and Sebastian Siebertz. Algorithmic properties of sparse digraphs. In Ro lf Niedermeier and Christophe Paul, editors, 36th International Symposium on Theoretical Aspects of Com puter Science, STACS 2019...

    2019

  18. [26]

    Structural properties and constant factor-approximation of strong di stance-r dominating sets in sparse directed graphs

    Stephan Kreutzer, Roman Rabinovich, Sebastian Siebertz, and Grischa Weberst¨ adt. Structural properties and constant factor-approximation of strong di stance-r dominating sets in sparse directed graphs. In 34th Symposium on Theoretical Aspects of Computer Science , volume 66 o...

    2017

  19. [27]

    The loop complexity of pure-group e vents

    Robert McNaughton. The loop complexity of pure-group e vents. Information and Control , 11:167–176, 1967

    1967

  20. [28]

    The loop complexity of regular even ts

    Robert McNaughton. The loop complexity of regular even ts. Information Sciences, 1(3):305– 328, 1969. 52

    1969

  21. [29]

    R ecognizing digraphs of kelly-width 2

    Daniel Meister, Jan Arne Telle, and Martin Vatshelle. R ecognizing digraphs of kelly-width 2. Discrete Applied Mathematics , 158(7):741–746, 2010

    2010

  22. [30]

    On the order of countable graphs

    Jaroslav Neˇ setˇ ril and Saharon Shelah. On the order of countable graphs. Eur. J. Comb. , 24(6):649–663, 2003

    2003

  23. [31]

    Tree-depth, subgraph coloring and homo- morphism bounds

    Jaroslav Ne˘ set˘ ril and Patrice Ossona de Mendez. Tree-depth, subgraph coloring and homo- morphism bounds. European J. Combin. , 27(6):1022–1041, 2006

    2006

  24. [32]

    Gradand classes with bounded expansion

    Jaroslav Ne˘ set˘ ril and Patrice Ossona de Mendez. Gradand classes with bounded expansion. I. Decompositions. European J. Combin. , 29(3):760–776, 2008

    2008

  25. [33]

    Gradand classes with bounded expansion

    Jaroslav Ne˘ set˘ ril and Patrice Ossona de Mendez. Gradand classes with bounded expansion. II. Algorithmic aspects. European J. Combin. , 29(3):777–791, 2008

    2008

  26. [34]

    Gradand classes with bounded expansion

    Jaroslav Ne˘ set˘ ril and Patrice Ossona de Mendez. Gradand classes with bounded expansion. III. Restricted graph homomorphism dualities. European J. Combin. , 29(4):1012–1024, 2008

    2008

  27. [35]

    Sparsity, volume 28 of Algorithms and Combinatorics

    Jaroslav Ne˘ set˘ ril and Patrice Ossona de Mendez. Sparsity, volume 28 of Algorithms and Combinatorics. Springer, Heidelberg, 2012. Graphs, structures, and algo rithms

    2012

  28. [36]

    Universal obstructions of graph parameters

    Christophe Paul, Evangelos Protopapas, and Dimitrios M Thilikos. Universal obstructions of graph parameters. arXiv preprint arXiv:2304.14121 , 2023

    2023 arXiv

  29. [37]

    T hilikos, and Sebastian Wiederrecht

    Christophe Paul, Evangelos Protopapas, Dimitrios M. T hilikos, and Sebastian Wiederrecht. Obstructions to Erd˝ os-P´ osa dualities for minors. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science—FOCS 2024 , pages 31–52. IEEE Computer Soc., Los Alamitos, CA, [...

    2024

  30. [38]

    Packing directed circuits

    Bruce Reed, Neil Robertson, Paul Seymour, and Robin Tho mas. Packing directed circuits. Combinatorica, 16(4):535–554, 1996

    1996

  31. [39]

    Neil Robertson and P. D. Seymour. Graph minors. I. Exclu ding a forest. J. Combin. Theory Ser. B , 35(1):39–61, 1983

    1983

  32. [40]

    Neil Robertson and P. D. Seymour. Graph minors. V. Exclu ding a planar graph. J. Combin. Theory Ser. B , 41(1):92–114, 1986

    1986

  33. [41]

    Linear-time algorithms for NP-complete problems restrict ed to partial k-trees , volume 87-3 of Rep., Akad

    Petra Scheffler. Linear-time algorithms for NP-complete problems restrict ed to partial k-trees , volume 87-3 of Rep., Akad. Wiss. DDR, Karl-Weierstraß-Inst. Math. Akademie der Wis- senschaften der DDR, Karl-Weierstraß-Institut f¨ ur Mathematik, Berlin, 1987

    1987

  34. [42]

    The structure of graphs not admitting a fixe d immersion

    Paul Wollan. The structure of graphs not admitting a fixe d immersion. J. Combin. Theory Ser. B , 110:47–66, 2015

    2015

  35. [43]

    H Younger

    D. H Younger. Graphs with interlinked directed circuit s. Proceedings of the Midwest Sym- posium on Circuit Theory , 2:XVI 2.1 – XVI 2.7, 1973

    1973

  36. [44]

    Colouring graphs with bounded generalized colouring number

    Xuding Zhu. Colouring graphs with bounded generalized colouring number. Discrete Math., 309(18):5562–5568, 2009. 53

    2009

Pith tools

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