pith. machine review for the scientific record. sign in

arxiv: 2605.12279 · v1 · submitted 2026-05-12 · 🧮 math.CO · cs.DM

Recognition: 2 theorem links

· Lean Theorem

Feedback vertex sets of planar digraphs with fixed digirth

Alexandre Pinlou, Petru Valicov, Simon Dreyer

Pith reviewed 2026-05-13 03:45 UTC · model grok-4.3

classification 🧮 math.CO cs.DM
keywords feedback vertex setplanar digraphdigirthcycle packingLucchesi-Younger theoremdirected graphsmin-max theorem
0
0 comments X

The pith

In planar digraphs of digirth g the minimum feedback vertex set has size at most (n-2)/(g-2).

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

The paper proves that any planar digraph on n vertices with no directed cycle shorter than length g has a feedback vertex set of size at most (n-2)/(g-2). This upper bound follows from a min-max theorem equating the smallest feedback vertex set to the largest collection of arc-disjoint cycles of a special type. The result is a planar-digraph version of the Lucchesi-Younger theorem. The authors also give explicit constructions of planar digraphs that achieve lower bounds close to n/g, which together tighten the known range for the maximum possible fraction of vertices in a minimum feedback vertex set.

Core claim

The authors prove that every planar digraph G of digirth g has a feedback vertex set of size at most (n-2)/(g-2). This follows from showing that the minimum size of a feedback vertex set is equal to the maximum number of arc-disjoint directed cycles that can be packed under the planarity constraint, providing a planar-digraph version of the Lucchesi-Younger min-max theorem. The bound is paired with constructions of infinite families of planar digraphs of fixed digirth g that force feedback vertex sets of size roughly n/g.

What carries the argument

The equality between the minimum feedback vertex set and the maximum packing of certain directed cycles in planar digraphs, serving as a planar analogue of the Lucchesi-Younger theorem.

If this is right

  • For every g at least 3, the supremum of fvs_g(n)/n over all n is at most 1/(g-2).
  • For g at least 6 the same supremum lies between (g+2)/g^2 and 1/(g-2), shrinking the previous gap by a factor of roughly g.
  • For g equal to 4 or 5 the new upper bound improves earlier estimates by an additive constant.
  • Infinite families of planar digraphs of any fixed digirth g at least 4 exist whose minimum feedback vertex sets are asymptotically at least (g+2)n/g^2 in size.

Where Pith is reading between the lines

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

  • The min-max equality may hold in digraph classes that are not planar but still forbid certain minors.
  • The cycle-connection construction technique could be adapted to produce lower-bound examples in other surface embeddings.
  • Computational checks on small instances would directly test whether the equality between feedback vertex set size and cycle packing holds in every planar digraph.

Load-bearing premise

That the minimum feedback vertex set size in a planar digraph is at most the maximum number of arc-disjoint cycles of the special type used in the packing.

What would settle it

A single planar digraph of digirth g in which the smallest feedback vertex set is strictly larger than (n-2)/(g-2), or strictly larger than the maximum size of a packing of the relevant directed cycles.

Figures

Figures reproduced from arXiv: 2605.12279 by Alexandre Pinlou, Petru Valicov, Simon Dreyer.

Figure 1
Figure 1. Figure 1: Construction of planar digraphs D of digirth g ≥ 4 and fvs(D) = n g−1 = 4. Observation 3. The digraphs of [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Examples of normal sets. The blue and red cycles are oriented clockwise and counterclockwise [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Construction of an infinite family of graphs with [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Example of three pairwise crossing cycles. [PITH_FULL_IMAGE:figures/full_fig_p008_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Transformations of two crossing oriented cycles (red and blue) into two non-crossing cycles [PITH_FULL_IMAGE:figures/full_fig_p008_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Example for computing the multiplicity of a vertex in some valuation [PITH_FULL_IMAGE:figures/full_fig_p012_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: A laminar valuation V with Root(TV ) = {C (1) 1 , C(1) 2 , C(1) 3 , C(1) 4 , C(1) 5 } and its inclusion forest TV . Given par ∈ {even, odd} and ori ∈ {clockwise, counterclockwise}, we define the following multiset of cycles: CV (par, ori) = {C ∈ CV | ℓ(C) has parity par and C is oriented ori}. We partition the multiset CV into two multisets according to the parity of the layer of the cycles and their orien… view at source ↗
Figure 8
Figure 8. Figure 8: Two half-arcs incident to v that are consecutive in GV (so ]e, e′ [= ∅) and that both belong to GV1 (or GV2 ) have opposite directions. Suppose now that S = {e1, . . . , ek} with k ≥ 1. Let C1 (respectively Ck) be the cycle that uses e1 (respectively ek). Since e and e ′ are consecutive in GV1 , then C1 ∈ C2 V (respectively Ck ∈ C2 V ). Then either ℓ(C) = ℓ(C1) and C and C1 have opposite orientations or |ℓ… view at source ↗
Figure 9
Figure 9. Figure 9: A digraph Gk of digirth g ≥ 4, satisfying fvs(Gk) = nk−1 g−1 Begin with G1, which is a directed cycle C (1) g = v 1 0 v 1 1 . . . v1 g−1 of length g oriented clockwise (with respect to a fixed planar embedding). For k ≥ 2, construct Gk from Gk−1 as follows: • Add a new directed cycle C (k) g = v k 0 v k 1 . . . vk g−1 of length g oriented clockwise. • Identify vertices v k g−1 of C (k) g with v k−1 1 of Gk… view at source ↗
Figure 10
Figure 10. Figure 10: Illustration of the proof of Proposition [PITH_FULL_IMAGE:figures/full_fig_p017_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: Building a coating H (in blue and green) of a skeleton graph G (in red). • If H is a coating of G, we say that G is the skeleton of H and by the previous item of the definition it is uniquely defined as a plane graph. • If f is a face of G whose incident vertices are in the same connected component of G, the vertices of H that lie inside f (excluding link vertices) form a cycle Cf oriented counterclockwis… view at source ↗
Figure 12
Figure 12. Figure 12: Left: an undirected graph G. Right: a coating H of G. The black cycles associated to the vertices of G are oriented clockwise. The link vertices and arcs are represented in green. 18 [PITH_FULL_IMAGE:figures/full_fig_p018_12.png] view at source ↗
Figure 13
Figure 13. Figure 13: Construction of a g-coating of digirth g for a subgraph of a skeleton G. Proof. Following Definition 26, we show that we can delete an edge (see Figure 13a) and delete a vertex (see Figure 13b) of the skeleton G and obtain a new coating H′ from the initial one H without reducing the digirth. (a) Let uv ∈ E(G), and let s ∈ V (H) be the link vertex associated to the edge uv. By splitting the vertex s into t… view at source ↗
Figure 14
Figure 14. Figure 14: Notations for the proof of Lemma 29. Let S1 = S − s + a1 and S2 = S − s + a2. If S1 is not a feedback vertex set of H, then there exists a directed cycle sb1 . . . a2s (because S is a feedback vertex set of H) that does not contain vertices of S1, in particular there is a directed path Pb1a2 from b1 to a2 in H − S. Similarly if S2 is not a feedback vertex set of H, then one can find a directed path Pb2a1 … view at source ↗
Figure 15
Figure 15. Figure 15: A skeleton graph G (in red) and 11 vertex-disjoint cycles of any coating of G (in green). The following remark, although not directly used in the proofs, is of independent interest as it highlights an inductive structure of skeletons and coatings. For example, it can be used to prove Corollary 30 using an induction on mG. Remark 32. Let H be a coating of some skeleton G. Let s be the link vertex associate… view at source ↗
Figure 16
Figure 16. Figure 16: ) • If u = v then H′ = H − s is a coating of G′ = G1 ⊎ G2 where G1 (resp. G2) is the graph induced by the edges lying in the exterior (resp. interior) of the loop uu (see [PITH_FULL_IMAGE:figures/full_fig_p021_16.png] view at source ↗
Figure 17
Figure 17. Figure 17: The deletion of a link vertex s of a coating H associated to a loop uu of a skeleton G, gives a coating H′ = H − s of the skeleton G′ = G1 ⊎ G2 obtained from G where the interior and exterior of uu are disconnected. The skeletons and coatings are drawn in red and blue respectively. Lemma 33. If H is a coating of digirth g of some skeleton graph G, then g · fvs(H) ≤ nH + mG. 21 [PITH_FULL_IMAGE:figures/fu… view at source ↗
Figure 18
Figure 18. Figure 18: The two types of degree 4 vertices of a coating. Left: link vertex [PITH_FULL_IMAGE:figures/full_fig_p022_18.png] view at source ↗
Figure 19
Figure 19. Figure 19: Left: a graph G with its corners. Right: a coating H of G with its associated coating function in blue. The black cycles associated to the vertices of G are oriented clockwise. Remark 38. Given a plane graph G and a coating function h, the following hold: • P c∈K h(c) = nH − mG. • The function h defines a g-coating if and only if for all v ∈ V (G), P c∈K(v) h(c) = g − d(v). The cycles associated to vertic… view at source ↗
Figure 20
Figure 20. Figure 20: A skeleton G (in red) with a coating function h (in blue) that satisfies the conditions of Observation 39 for g = 8 but nevertheless the corresponding coating contains a directed cycle of length 7 (in purple). 23 [PITH_FULL_IMAGE:figures/full_fig_p023_20.png] view at source ↗
Figure 21
Figure 21. Figure 21: A g-coating H of the skeleton graph G = C4 with its associated coating function in blue. The black cycles associated to the vertices of G are oriented clockwise. Application 40. Consider a g-coating H of digirth g ≥ 4 of the skeleton graph G = C4 (undirected 4-cycle) with the following coating function defined in [PITH_FULL_IMAGE:figures/full_fig_p024_21.png] view at source ↗
Figure 22
Figure 22. Figure 22: The family (Gk)k≥0 of Section 3.4.1 and its coating function in blue. For all k ≥ 0, Hk is a 6-coating. To prove that (Hk)k≥0 is a family of coatings of digirth 6, we apply Lemma 44, which requires the following. Observation 46. (1) H0 and H1 have digirth 6. (2) For any two link vertices y, z associated to edges of the cycle u0v0w0x0, we have dH0 (y, z) = dH1 (y, z). Observation 46(1) can be verified by h… view at source ↗
Figure 23
Figure 23. Figure 23: The family (Gk)k≥0 of Section 3.4.2 and its coating function in blue. For all k ≥ 0, Hk is an 8-coating. To prove that (Hk)k≥0 is a family of coatings of digirth 8, we apply Lemma 44, which requires the following. Observation. (1) H0 and H1 have digirth 8. (2) For any two link vertices y, z associated to edges of the cycle u0v0w0x0, we have dH0 (y, z) = dH1 (y, z). Both items can be verified by hand or wi… view at source ↗
Figure 24
Figure 24. Figure 24: A skeleton (in red) with a loop and two directed cycles of a coating formed by the link [PITH_FULL_IMAGE:figures/full_fig_p029_24.png] view at source ↗
Figure 25
Figure 25. Figure 25: Left: a coating H of a skeleton G and a directed cycle D (in purple) of H. Right: The subgraphs G ∩ D− and H ∩ D−. G′ is connected. The cycle D corresponds to a closed walk on G via a sequence of corners (c1, . . . , ck) incident to vertices (v1, . . . , vℓ) of G′ : consecutive corners either share the same vertex of G (turning around it) or are connected by an edge of G (crossing into D−). Hence all of v… view at source ↗
Figure 26
Figure 26. Figure 26: Base blocks and construction of the family [PITH_FULL_IMAGE:figures/full_fig_p032_26.png] view at source ↗
Figure 27
Figure 27. Figure 27: A coating function for Gk ℓ (in blue) yielding a perfect g-coating for g = 8k + 4. One can verify that this coating function satisfies the conditions of Definition 47 that is the h(c) around a face sum to g = 8k + 4 and the h(c) around a vertex v sum to g − d(v). 33 [PITH_FULL_IMAGE:figures/full_fig_p033_27.png] view at source ↗
Figure 28
Figure 28. Figure 28: Coloring of the half-edges of Gk ℓ . The special edges of each of the four colors are those labelled Si for 1 ≤ i ≤ 8. The color of label Si corresponds to the color the edge is special for. Denote by Ec the set of edges of Gk ℓ having one half-edge colored c (see [PITH_FULL_IMAGE:figures/full_fig_p035_28.png] view at source ↗
Figure 29
Figure 29. Figure 29: Forest Ered in the graph Gk ℓ . Observation 58. (i) There is no edge of Gk ℓ whose two half-edges have the same color. Thus every edge of Gk ℓ belongs to exactly two of the sets Ec. Moreover, there are equally many half-edges of each color in Gk ℓ . Hence, from Remark 54 |Eblack| = |Ered| = |Eblue| = |Egreen| = |E(Gk ℓ )| 2 = ℓ · (4k + 2) (ii) Let c be a color among red, blue, black, and green. Ec contain… view at source ↗
Figure 30
Figure 30. Figure 30: The family (Gk)k≥0 of Section A.1 and its coating function in blue. For all k ≥ 0, Hk is a 9-coating. To prove that (Hk)k≥0 is a family of coatings of digirth 9, we use Lemma 44. Observation. (1) H0 and H1 have digirth 9. (2) For two link vertices y, z associated with edges of the cycle u0v0w0x0, we have dH0 (y, z) = dH1 (y, z). These observations can be verified by hand or with a computer. Hence we can a… view at source ↗
Figure 31
Figure 31. Figure 31: The family (Gk)k≥0 of Section A.2 and its coating function in blue. For all k ≥ 0, Hk is a 10-coating. To prove that (Hk)k≥0 is a family of coatings of digirth 10, we use Lemma 44. Observation. (1) H0 and H1 have digirth 10. (2) For two link vertices y, z associated with edges of the cycle u0v0w0x0, we have dH0 (y, z) = dH1 (y, z). These observations can be verified by hand or with a computer. Hence we ca… view at source ↗
Figure 32
Figure 32. Figure 32: The family (Gk)k≥0 of Section A.3 and its coating function in blue. For all k ≥ 0, Hk is an 11-coating. To prove that (Hk)k≥0 is a family of coatings of digirth 11, we use Lemma 44. Observation. (1) H0 and H1 have digirth 11. (2) For two link vertices y, z associated with edges of the cycle u0v0w0x0, we have dH0 (y, z) = dH1 (y, z). These observations can be verified by hand or with a computer. Hence we c… view at source ↗
Figure 33
Figure 33. Figure 33: Base blocks and construction of the family [PITH_FULL_IMAGE:figures/full_fig_p046_33.png] view at source ↗
Figure 34
Figure 34. Figure 34: A coating function h for G k,r ℓ yielding a perfect g-coating. We only write the coating function around the newly added vertices and edges. For the other corners h(c) is either h0(c) or h0(c) + x with x ∈ {r, r − b, b} and h0 being the coating function defined in [PITH_FULL_IMAGE:figures/full_fig_p047_34.png] view at source ↗
Figure 35
Figure 35. Figure 35: Coloring of the half-edges of G k,r ℓ . We also give the two special edges for each color in S a and in the blocks Bx (x = a or a + b) For c a color among (black, red, blue, green), denote by Ec the set of edges of G k,r ℓ having one half-edge colored c (see [PITH_FULL_IMAGE:figures/full_fig_p049_35.png] view at source ↗
Figure 36
Figure 36. Figure 36: Forest Ered in the graph G k,r ℓ . The properties of Observation 58 still hold and we add some more to deal with the edges incident to the added vertices (v (i) j ) 1≤j≤a+b 0≤i≤2ℓ−1 . 49 [PITH_FULL_IMAGE:figures/full_fig_p049_36.png] view at source ↗
read the original abstract

Let $fvs(G)$ denote the size of a minimum feedback vertex set of a digraph $G$. We study $fvs_g(n)$, which is the maximum $fvs(G)$ over all $n$-vertex planar digraphs $G$ of digirth $g$. It is known in the literature that $\lfloor\frac{n-1}{g-1}\rfloor \le fvs_g(n)$ and $fvs_3(n)\le \frac{3n}{5}$, $fvs_4(n)\le \frac{n}{2}$, $fvs_5(n)\le \frac{2n-5}{4}$ and $\lfloor\frac{n-1}{g-1}\rfloor \le fvs_g(n) \le \frac{2n-6}{g}$ for $g \ge 6$. In particular for $g \ge 6$, $\frac{1}{g-1}\le \sup_{n \ge 1} \frac{fvs_g(n)}{n} \le \frac{2}{g}$. We improve all lower and upper bounds starting with digirth 4. Namely, we show that $fvs_g(n)\le \frac{n-2}{g-2}$ for all $g\geq 3$, by proving that the minimum feedback vertex set is at most the maximum packing of a special type of directed cycles. This last result is a planar-digraph analogue of the celebrated Lucchesi-Younger theorem and is of independent interest. On the other hand, we develop a new tool to construct planar digraphs of fixed digirth and large $fvs$ by connecting arc-disjoint directed cycles. Using it, we provide constructions of infinite families of planar digraphs of digirth $g\ge 4$ and large $fvs$. These constructions together with our upper bound show that $\frac{g+2}{g^2} \le \sup_{n \ge 1} \frac{fvs_g(n)}{n} \le \frac{1}{g-2}$ for all values $g \ge 6$, except $g =7$, for which the lower bound is different. We thus decrease the gap between the lower and the upper bound for $\sup_{n \ge 1} \frac{fvs_g(n)}{n}$ from $\frac{g-2}{g(g-1)}$ to $\frac{4}{g^2(g-2)}$. For $g = 7$ this gap goes from $\frac{5}{42}$ to $\frac{1}{55}$. For digirth 4 and 5, both improvements are by an additive constant.

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 studies the function fvs_g(n), defined as the largest possible size of a minimum feedback vertex set in an n-vertex planar digraph with digirth g. It proves a new upper bound fvs_g(n) ≤ (n-2)/(g-2) for g ≥ 3 by establishing a min-max theorem equating (or bounding) the minimum feedback vertex set size to the maximum packing of certain special directed cycles, which is presented as a planar digraph version of the Lucchesi-Younger theorem. The paper also introduces a construction technique for connecting arc-disjoint directed cycles to create planar digraphs with fixed digirth and large feedback vertex sets, leading to improved lower bounds on the asymptotic ratio sup fvs_g(n)/n for g ≥ 4 and a reduced gap between lower and upper bounds on this ratio.

Significance. If the proofs hold, this paper makes a valuable contribution to extremal graph theory for directed planar graphs. The analogue of the Lucchesi-Younger theorem provides a new structural tool for planar digraphs, and the explicit constructions allow for concrete improvements in the known bounds, narrowing the gap in the density from (g-2)/(g(g-1)) to 4/(g^2(g-2)) for g ≥ 6 (with a special case for g=7). The work is of independent interest due to the cycle packing result.

minor comments (2)
  1. Abstract: the lower bound for g=7 is described only as 'different' without stating the explicit value; adding the precise expression would improve completeness.
  2. Section introducing the min-max theorem: the precise definition of the 'special type of directed cycles' should be stated with formal notation immediately upon first use to aid readers.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive and accurate summary of our manuscript, as well as for recommending minor revision. The report correctly captures the main results, including the new upper bound via the planar-digraph analogue of the Lucchesi-Younger theorem and the improved constructions narrowing the asymptotic gap.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper proves its key upper bound fvs_g(n) ≤ (n-2)/(g-2) by establishing a new min-max relation (min FVS size ≤ max packing of special directed cycles) that is proved directly in the manuscript as a planar-digraph analogue of Lucchesi-Younger; this is an independent theorem rather than a self-definition or fitted input. Lower-bound constructions rely on explicit arc-disjoint cycle connections whose planarity and exact digirth are verified by direct embedding arguments, not by renaming known results or smuggling ansatzes via self-citation. No load-bearing self-citations, no uniqueness theorems imported from the authors' prior work, and no reduction of any claimed prediction to its own inputs by construction. The derivation chain is self-contained.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

This is a pure combinatorial graph-theory paper. It relies on standard definitions of planarity, digraphs, and directed cycles with no free parameters, no invented entities, and only domain assumptions from established graph theory.

axioms (1)
  • domain assumption Planar digraphs admit embeddings in the plane without arc crossings, and digirth is the length of the shortest directed cycle.
    These are the foundational definitions used throughout the statements of fvs_g(n) and the constructions.

pith-pipeline@v0.9.0 · 5825 in / 1431 out tokens · 137282 ms · 2026-05-13T03:45:13.952360+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

25 extracted references · 25 canonical work pages

  1. [1]

    Akiyama and M

    J. Akiyama and M. Watanabe. Maximum induced forests of planar graphs.Graphs and Combinatorics, 3(1):201–202, 1987

    work page 1987

  2. [2]

    Albertson and D.M

    M.O. Albertson and D.M. Berman. A conjecture on planar graphs. InGraph Theory and Related Topics (J.A. Bondy and U.S.R. Murty, eds.). Academic Press, 1976

    work page 1976

  3. [3]

    Bonamy, F

    M. Bonamy, F. Kardoš, T. Kelly, and L. Postle. Fractional vertex-arboricity of planar graphs, 2020

    work page 2020

  4. [4]

    O.V. Borodin. On acyclic colorings of planar graphs.Discrete Mathematics, 25(3):211–236, 1979

    work page 1979

  5. [5]

    Dross, M

    F. Dross, M. Montassier, and A. Pinlou. A lower bound on the order of the largest induced forest in planar graphs with high girth.Discrete Applied Mathematics, 214:99–107, 2016

    work page 2016

  6. [6]

    Esperet, L

    L. Esperet, L. Lemoine, and F. Maffray. Small feedback vertex sets in planar digraphs.Electronic Journal of Combinatorics, 24(2), 2017

    work page 2017

  7. [7]

    M. R. Garey and D. S. Johnson.Computers and Intractability: A Guide to the Theory of NP-Completeness (Series of Books in the Mathematical Sciences). W. H. Freeman, 1979

    work page 1979

  8. [8]

    M. X. Goemans and D. P. Williamson. Primal-dual approximation algorithms for feedback problems in planar graphs.Combinatorica, 18(1):37–59, 1998

    work page 1998

  9. [9]

    R. M. Karp. Reducibility among combinatorial problems. In Raymond E. Miller and James W. Thatcher, editors,Complexity of Computer Computations, pages 85–103. Plenum Press, New York, 1972. 41

    work page 1972

  10. [10]

    Kelly and C.-H

    T. Kelly and C.-H. Liu. Minimum size of feedback vertex sets of planar graphs of girth at least five.European Journal of Combinatorics, 61:138–150, 2017

    work page 2017

  11. [11]

    Knauer, P

    K. Knauer, P. Valicov, and P. S. Wenger. Planar digraphs without large acyclic sets.Journal of Graph Theory, 85(1):288–291, 2017

    work page 2017

  12. [12]

    Kowalik, B

    Ł. Kowalik, B. Lužar, and R. Škrekovski. An improved bound on the largest induced forests for triangle-free planar graphs.Discrete Mathematics & Theoretical Computer Science, 12:87–100, 2010

    work page 2010

  13. [13]

    H. Le. A better bound on the largest induced forests in triangle-free planar graphs.Graphs and Combinatorics, 34:1217–1246, 2018

    work page 2018

  14. [14]

    Li and B

    Z. Li and B. Mohar. Planar digraphs of digirth four are 2-colorable.SIAM Journal on Discrete Mathematics, 31(3):2201–2205, 2017

    work page 2017

  15. [15]

    L. Lovász. On two minimax theorems in graph.Journal of Combinatorial Theory, Series B, 21(2):96–103, 1976

    work page 1976

  16. [16]

    C. L. Lucchesi and D. H. Younger. A minimax theorem for directed graphs.Journal of the London Mathematical Society, 2(17):369–374, 1978

    work page 1978

  17. [17]

    B. Mohar. Acyclic partitions of planar digraphs. Problem of the Month, July 2002, July 2002. Accessed: 2025-10-28

    work page 2002

  18. [18]

    Neumann-Lara

    V. Neumann-Lara. Vertex colourings in digraphs. some problems. Technical report, University of Waterloo, July 8 1985

    work page 1985

  19. [19]

    E. R. Scheinerman and D. H. Ullman.Fractional Graph Theory: A Rational Approach to the Theory of Graphs. Courier Corporation, 2013

    work page 2013

  20. [20]

    Shi and H

    L. Shi and H. Xu. Large induced forests in graphs.Journal of Graph Theory, 85(4):759–779, 2017

    work page 2017

  21. [21]

    D. B. West. Induced acyclic subgraphs in planar digraphs, 2006.https://dwest.web.illinois. edu/regs/plandifor.html. 42 Appendix A Proof of Theorem 45 A.1 Theorem 45(iii): caseg= 9 Consider the recursive coating family(Hk)k≥0of the skeleton(Gk)k≥0defined in Figure 30. The coating function is defined in blue in the figure. For every integerk≥0, Figure 30 gi...

    work page 2006

  22. [22]

    Ak 2i−1) are identified with vertices of layer 45 0 of the blockBa 2i (resp

    The vertices of layer 0 of the blockAk 2i (resp. Ak 2i−1) are identified with vertices of layer 45 0 of the blockBa 2i (resp. Ba+b 2i−1). The vertices of layerk−1of the block Ba 2i (resp. Ba+b 2i−1) are identified with vertices of layerk−1of the blockAk 2i+1 (resp. Ak 2i). The construction is illustrated in Figure 33d. k − 1 0 1 2 k − 2 (a) BlockA k withk...

    work page

  23. [23]

    Ak 2i) can be identified with a unique edge ofA k 1 (resp.A k 2)

    So every edge ofAk 2i−1(resp. Ak 2i) can be identified with a unique edge ofA k 1 (resp.A k 2). •For1 ≤i≤ℓ, every colored blockBa+b 2i−1is identical toBa+b 1 . So every edge ofBa+b 2i−1can be identified with a unique edge ofBa+b 1 . •For1 ≤i≤ℓ−1, every edge in blockBa 2i incident to a vertexv(2i) j (for1 ≤j≤a) can be identified with a unique edge ofSa inc...

    work page

  24. [24]

    Denote byc 1,c 2 the color of the two half-edges offe

    To reach the remaining weight 2 g+2, distinguish multiple cases depending on the nature offe. Denote byc 1,c 2 the color of the two half-edges offe. 51 •If fe is inAk 1 or Ak 2 then e is used inTc,x1,x2 when c /∈{c1,c 2}and fe∈{x1,x 2}. Ifb = 0or if {c1,c 2}̸={black,blue}and{c1,c 2}̸={red,green}then it contributes to two trees of weight 1 g+2. If b = 1and...

    work page

  25. [25]

    Thus the total contribution is 2 g+2

    From Observation 71(i), this contributes to2k trees of weight b k(g+2). Thus the total contribution is 2 g+2. Thuseis contained in trees ofAof total weight at least 1. HenceAis a 2g g+2-arborization ofGk,r ℓ. Theorem 57 together with Remark 69 show thataf(Gk,r ℓ) = 2g g+2 forg= 8k+ 4 + 2a+b. Finally we can prove Lemma 61. Lemma.For allg≥12, there exists a...

    work page