Pith. sign in

REVIEW 2 major objections 2 minor 42 references

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

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

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

Pith's one-line read For any fixed circle graph H with at least one edge and any positive integer k, every graph either contains k disjoint vertex-minor copies of H or has a bounded perturbation with no vertex-minor copy of H.

desk verdict The main theorem is not established as written: Lemma 5.1's induction invariant fails, so the proof collapses, though the perturbation framework is promising. read the letter →

arxiv 2506.03973 v1 pith:L4M3N32A submitted 2025-06-04 math.CO

Rutger Campbell , J. Pascal Gollin , Meike Hatzel , O-joung Kwon , Rose McCarty , Sang-il Oum , Sebastian Wiederrecht This is my paper
classification math.CO MSC 05C8305C7505B35
keywords circlegraphsvertex-minorsErdős-Pósapropertyrank-widthperturbationspivot-minorsbinarymatroidslocalcomplementation
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

The paper proves that circle graphs have an Erdős-Pósa property for vertex-minors. Concretely, for every fixed circle graph $H$ with at least one edge and every positive integer $k$ there is a bound $t=t(k,H)$ such that every graph $G$ either has a vertex-minor isomorphic to the disjoint union $kH$, or has a $t$-perturbation with no vertex-minor isomorphic to $H$. This matters because it transplants the classical packing-versus-covering dichotomy from graph minors to the local-complementation world, where the appropriate notion of a small modification is a low-rank perturbation rather than deleting a hitting set. The same machinery yields an analogous dichotomy for binary matroids: for any planar multigraph $H$, every binary matroid either has a minor isomorphic to the cycle matroid of $kH$ or can be perturbed by low rank to one avoiding the cycle matroid of $H$.

What carries the argument

The load-bearing object is a robust part: a graph $F$ is $t$-robust for $H$ if every $t$-perturbation of $F$ still has $H$ as a vertex-minor. The proof's engine is a two-stage decomposition: Proposition 4.2 either hands back a bounded perturbation deleting one component of $H$, or produces many pairwise disjoint robust parts of bounded size whose cut-rank is at most $r(m^2+1)$; Proposition 5.2 then orders these parts into a uniform chain and fixes, one by one in lexicographic order, every pair of coordinate positions by Ramsey selection followed by local complementation or edge pivots. Once all pairs are fixed, distinct parts have no edges between them, and each part still contains every component of $H$ as a vertex-minor because robustness degrades only by the bounded perturbation supplied by Lemma 3.4. For matroids, the corresponding mechanism replaces local complementation by pivoting in bipartite fundamental graphs and uses Bouchet's fundamental-graph correspondence between pivot-minors and binary matroid minors.

What would settle it

A concrete check: build a chain satisfying Lemma 5.1's hypotheses in which the $j_2$-th pivot endpoint is adjacent to a vertex in an already fixed set, or in which the first pivot removes the edge the second pivot needs. Running the lemma's described pivot sequence and inspecting whether any earlier fixed pair toggles would decide whether Lemma 5.1, and with it Proposition 5.2 and Theorem 1.1, is supported by the proof.

Watch

Extended reading notes

Core claim

Theorem 1.1 is the central claim: for a circle graph $H$ with at least one edge and an integer $k \geq 1$, there exists $t=t(k,H)$ so that every graph $G$ either contains as a vertex-minor the disjoint union of $k$ copies of $H$, or some $t$-perturbation of $G$ has no vertex-minor isomorphic to $H$. The proof first invokes the Grid Theorem for Vertex-Minors to force $G$ into bounded rank-width once $kH$ is excluded, then alternates between two outcomes: a perturbation avoiding a component of $H$, or many pairwise disjoint, bounded-size robust parts with cut-rank bounded independently of $t$. A Ramsey-type extraction procedure fixes all cross-edges between these parts and assembles $kH$. The same proof, reworked with pivots in bipartite graphs, gives the matroid corollary: for every planar multigraph $H$, each binary matroid $M$ either has a minor isomorphic to $M(kH)$ or a rank-$p$ perturbation with no minor isomorphic to $M(H)$.

Load-bearing premise

The whole argument hangs on the claim in Lemma 5.1 that the Ramsey-type pivot procedure can fix pairs one at a time while leaving already fixed pairs untouched, but the verification shown tracks only one endpoint of each pivot.

Editorial extensions

If this is right

  • If Theorem 1.1 is correct, then for every fixed circle graph $H$ with an edge, forbidding $k$ disjoint vertex-minor copies of $H$ is equivalent, up to bounded perturbation, to forbidding a single copy of $H$.
  • The matroid corollary says binary matroids over the cycle matroid of a fixed planar multigraph satisfy a packing-covering dichotomy with low-rank perturbations as the covering notion.
  • The rough converses (Propositions 1.2 and 10.6) make the bounds qualitatively tight: a $t$-perturbation avoiding $H$ blocks packing $(t+1)H$, so the theorem's dependence on $t$ is not an artifact.
  • Perturbations are essential: Lemma 7.3 gives graphs with no $2P_4$ vertex-minor whose every local-equivalent graph minus any $t$ vertices still contains $P_4$, so no $0$-perturbation plus vertex-deletion version of Theorem 1.1 holds.
  • Since $kH$ is a circle graph whenever $H$ is, the Grid Theorem for Vertex-Minors is the only place the circle-graph hypothesis is used; if a non-circle $H$ ever satisfies the grid theorem, the same proof would give the property for $H$.

Reading between the lines

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

  • Editorial: The suspected positive answer to Problem 1.3 would mark a genuine divergence from the minor setting, where non-planar graphs fail the Erdős-Pósa property; proving it would likely require a different source of bounded rank-width than the grid theorem.
  • Editorial: The proof's dependence on the well-quasi-ordering theorem gives huge, non-constructive constants for $t(k,H)$; replacing that step with an explicit bound would turn the theorem into an algorithm for finding either $kH$ or the perturbation.
  • Editorial: The robust-parts dichotomy may transfer to other binary-matrix flip operations studied in logic and monadic stability, yielding structural dichotomies for graph classes definable by such flips.
  • Editorial: Lemma 5.1's safety claim is checkable in isolation; if a repair exists, Theorem 1.1 may still survive with a different pivot schedule or additional fixed-pair invariants.
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 / 2 minor

Summary. The paper proves Theorem 1.1: for every circle graph H with at least one edge and every positive integer k, there is an integer t=t(k,H) such that every graph G either has a vertex-minor isomorphic to kH or has a t-perturbation with no vertex-minor isomorphic to H. It also proves an analogous pivot-minor statement for bipartite circle graphs and derives Corollary 1.4 for binary matroids. The proof strategy is to reduce to bounded rank-width via the Grid Theorem for Vertex-Minors, find many small robust parts of small cut-rank via Proposition 4.2, then use Lemma 5.1 to locally complement or pivot so that cross-edges between these parts disappear, and finally use robustness to extract kH. The matroid results are obtained by translating the bipartite pivot-minor theorem through fundamental graphs.

Significance. If correct, this is a substantial step: it provides an Erdős-Pósa-type theorem for vertex-minors, introduces perturbations as the appropriate replacement for hitting sets, and gives a matroid analogue for planar multigraphs. The use of external black boxes such as the Grid Theorem for Vertex-Minors and Oum's well-quasi-ordering theorem is appropriate, and the paper is generally well organized. However, the proof of the central extraction step, Lemma 5.1, contains a nontrivial gap that is load-bearing for Theorem 1.1 and for the matroid results.

major comments (2)
  1. [Section 5, Lemma 5.1, up-coupled half-graph case] The induction invariant in the up-coupled case is false. Write A_i=Z_i(j1) and B_i=Z_i(j2), and take the canonical up-coupled half-graph on Z_1,...,Z_9 with the additional choices that B_1B_4 is present and B_2B_4 is absent. After the first pivot on B_1A_3, the edge B_2B_4 is toggled from absent to present: B_2 is adjacent to A_3 and not to B_1, while B_4 is adjacent to B_1 and not to A_3, so the two endpoints have different neighbor sets in {u,v}. Thus a j2-vertex of the first remaining part Z_2 has an edge to a j2-vertex of the later part Z_4 in eG_1. This directly contradicts the claim that eG_i has no edge joining the j1th or j2th vertex of any of the first i parts of Y_i to any j1th or j2th vertex in a different part of Y_i, and it invalidates the step in which the proof says 'we only need to worry about the later parts'. The subsequent assertion that the only j2-vertex in N_{eG_i}(v) is Y_{3i+2}(j2) is therefore unsupported. Since the proof of Lemma 5.1 is the mechanism that fixes all cross pairs in Proposition 5.2, and Theorem 1.1 depends on Proposition 5.2, the main theorem is not established as written.
  2. [Sections 5, 9, and 10] The gap in Lemma 5.1 propagates to the rest of the paper. Proposition 5.2 applies Lemma 5.1 to conclude that the parts Y_j are pairwise non-adjacent in eG; without a valid proof of Lemma 5.1, this conclusion is not justified, and the final extraction of kH in Theorem 1.1 does not follow from the stated arguments. The same flawed pivot-sequence argument is used in Lemma 9.7 and Proposition 9.8, so Theorem 9.9 and Corollary 1.4 inherit the same defect. A repair of the extraction lemma would be needed to restore the proofs of all three main results.
minor comments (2)
  1. [Proposition 5.2 and Proposition 9.8] The quantifier in the hypothesis 'for all i in [m] and j in [k]' should read 'for all i in [m] and j in [K]', since the sets X_{i,j} are indexed by [K] and the subsequent argument uses all K indices.
  2. [Lemma 10.3, proof] The proof says 'Fix an arbitrary vertex v of G which is not an element of M1', but if G has exactly |E(M1)| vertices then no such vertex exists. This case is easily handled by the p=0 case, but it should be stated explicitly.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the proof derives Theorem 1.1 from independently established grid theorems and well-quasi-ordering results, and its internal extraction lemmas are not restatements of the conclusion.

full rationale

The derivation chain is self-contained and non-circular. Theorem 1.1 is reduced, via the Grid Theorem for Vertex-Minors [GKMW23], to the bounded-rank-width case; Proposition 4.2 then produces either the desired perturbation or many small robust parts using only perturbation lemmas (Lemmas 3.1–3.4) and Oum's well-quasi-ordering theorem [Oum08]. Proposition 5.2 extracts kH from those robust parts by a Ramsey-type fixing procedure (Lemma 5.1) and perturbation robustness arguments. None of these steps defines the target Erdős-Pósa statement in terms of itself, and no parameter is fitted to data and then renamed a prediction. The proof does rely on self-citations: [GKMW23] includes coauthor McCarty and [Oum08] includes coauthor Oum, but both are independent published theorems used as black boxes, and neither assumes the present theorem or its perturbation conclusion. The skeptical concern about Lemma 5.1's induction invariant, if valid, would be a correctness gap in the proof, not a circularity: the lemma is a genuine combinatorial extraction step and is not equivalent to Theorem 1.1 by construction. No circular step is exhibited. Therefore the circularity score is 0.

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

The paper introduces new definitions (t-perturbation, t-robustness) but these are mathematical concepts, not invented physical entities. The proof relies on several deep external theorems from the literature, listed above. No free parameters are fitted to data.

assumptions (9)
  • domain assumption Grid Theorem for Vertex-Minors (Theorem 2.2, Geelen-Kwon-McCarty-Wollan): for any circle graph H, graphs with no H vertex-minor have bounded rank-width.
    Used to reduce the host graph G to bounded rank-width in the proof of Theorem 1.1.
  • domain assumption Oum's well-quasi-ordering theorem (Theorem 2.3): bounded rank-width graphs are well-quasi-ordered under pivot-minors.
    Used to show finiteness of minimal robust graphs in Proposition 4.2.
  • standard math Ramsey's theorem (used implicitly for chains and half-graphs).
    Used in Lemma 5.1 and Proposition 5.2 to find monochromatic subchains.
  • domain assumption Bipartite Ramsey theorem (Theorem 10.1, Beineke-Schwenk).
    Used in the proof of Corollary 1.4 for the case where H has no cycles of length at least 2.
  • domain assumption Geelen-Gerards-Whittle grid theorem for GF(q)-representable matroids (Theorem 8.3).
    Used to bound rank-width of bipartite graphs with no pivot-minor for Theorem 9.9.
  • domain assumption Geelen-Gerards-Whittle well-quasi-ordering for matroids (Theorem 8.4).
    Used in Proposition 9.6 to bound the size of minimal pivot-robust parts.
  • domain assumption de Fraysseix characterization: fundamental graphs of planar multigraphs are exactly bipartite circle graphs (Theorem 8.2).
    Used to connect pivot-minors of bipartite graphs to minors of cycle matroids of planar graphs.
  • domain assumption Bouchet's correspondence between pivot-minors and matroid minors (Lemma 8.1).
    Used to translate between bipartite pivot-minors and binary matroid minors.
  • domain assumption Geelen-Gerards-Whittle lemma on rank-p perturbations and distance (Lemma 10.2).
    Used in Corollary 1.4 and Proposition 10.6 to relate pivot-perturbations to rank perturbations.

how reviews work

0 comments
Cite this review

Pith. "Pith review of The Erd\H{o}s-P\'{o}sa property for circle graphs as vertex-minors." pith.science (2026). https://pith.science/paper/L4M3N32A

@misc{pith2026250603973,
  author       = {Pith},
  title        = {Pith review of: The Erd\Hos-P\'osa property for circle graphs as vertex-minors},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/L4M3N32A}},
  note         = {Machine review of arXiv:2506.03973}
}
abstract

We prove that for any circle graph $H$ with at least one edge and for any positive integer $k$, there exists an integer $t=t(k,H)$ so that every graph $G$ either has a vertex-minor isomorphic to the disjoint union of $k$ copies of $H$, or has a $t$-perturbation with no vertex-minor isomorphic to $H$. Using the same techniques, we also prove that for any planar multigraph $H$, every binary matroid either has a minor isomorphic to the cycle matroid of $kH$, or is a low-rank perturbation of a binary matroid with no minor isomorphic to the cycle matroid of $H$.

Figures

Figures reproduced from arXiv: 2506.03973 by the authors.

Figure 1
Figure 1. A chord diagram and its corresponding circle graph. [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Local complementation and pivoting. of u and v. The resulting graph is denoted by G × uv. See [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. Coupled pairs (j1, j2) with j1 ̸= j2. Two vertices in the same set Xi ∈ X may or may not be adjacent, and this is presented by a dashed line. graph Ge[Xi,j ] = Gm,k[Xi,j ] is t-robust for Hi . We know from construction that Gi,j [Xi,j ] is (t + ℓ)-robust for Hi . Consider the graph G′ obtained from Gi,j by deleting the vertices in Yi,j \Xi,j . Notice that ρG′(Xi,j ) ⩽ ρGb(Yi,j ) ⩽ r(m2 + 1). Also notice that, since … view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: The procedure of fixing a pair (j1, j2) with j1 < j2 that is an up-coupled half graph in Lemma 5.1. The graph Ge2 is obtained from Ge1 by pivoting the edge joining Z4(j2) and Z6(j1), which is depicted as an edge marked in red. Note that Y1(j1) is independent in Ge1, an…

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

42 extracted references · 21 canonical work pages

  1. [1]

    Pascal Gollin, Tony Huynh, and O - joung Kwon

    Jungho Ahn, J. Pascal Gollin, Tony Huynh, and O - joung Kwon. A coarse E rdős- P ósa theorem. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 3363--3381, 2025. https://doi.org/10.1137/1.9781611978322.109 doi:10.1137/1.9781611978322.109

    doi:10.1137/1.9781611978322.109 2025

  2. [2]

    Interlace polynomials

    Martin Aigner and Hein van der Holst . Interlace polynomials. Linear Algebra and its Applications , 377:11--30, 2004. https://doi.org/10.1016/j.laa.2003.06.010 doi:10.1016/j.laa.2003.06.010

    work page doi:10.1016/j.laa.2003.06.010 2004

  3. [3]

    Isotropic systems

    Andr \'e Bouchet. Isotropic systems. European J. Combin. , 8(3):231--244, 1987. https://doi.org/10.1016/S0195-6698(87)80027-6 doi:10.1016/S0195-6698(87)80027-6

    doi:10.1016/s0195-6698(87)80027-6 1987

  4. [4]

    Graphic presentations of isotropic systems

    Andr \'e Bouchet. Graphic presentations of isotropic systems. J. Combin. Theory Ser. B , 45(1):58--76, 1988. https://doi.org/10.1016/0095-8956(88)90055-X doi:10.1016/0095-8956(88)90055-X

    doi:10.1016/0095-8956(88)90055-x 1988

  5. [5]

    Beineke and Allen J

    Lowell W. Beineke and Allen J. Schwenk. On a bipartite form of the R amsey problem. In Proceedings of the F ifth B ritish C ombinatorial C onference ( U niv. A berdeen, A berdeen, 1975) , pages 17--22. Congressus Numerantium, No. XV, Winnipeg, Man., 1976. Utilitas Math

    work page 1975

  6. [6]

    Large-treewidth graph decompositions and applications

    Chandra Chekuri and Julia Chuzhoy. Large-treewidth graph decompositions and applications. In S TOC '13--- P roceedings of the 2013 ACM S ymposium on T heory of C omputing , pages 291--300. ACM, New York, 2013. https://doi.org/10.1145/2488608.2488645 doi:10.1145/2488608.2488645

    arXiv 2013

  7. [7]

    A tight E rd o s- P \'o sa function for planar minors

    Wouter Cames van Batenburg, Tony Huynh, Gwena\"el Joret, and Jean-Florent Raymond. A tight E rd o s- P \'o sa function for planar minors. Adv. Comb. , pages Paper No. 2, 33, 2019. https://doi.org/10.19086/aic.10807 doi:10.19086/aic.10807

    doi:10.19086/aic.10807 2019

  8. [8]

    Dabrowski, Fran c ois Dross, Jisu Jeong, Mamadou Moustapha Kant\' e , O - joung Kwon, Sang - il Oum, and Dani\" e l Paulusma

    Konrad K. Dabrowski, Fran c ois Dross, Jisu Jeong, Mamadou Moustapha Kant\' e , O - joung Kwon, Sang - il Oum, and Dani\" e l Paulusma. Computing pivot-minors. preprint, 2023. https://arxiv.org/abs/2311.04656 arXiv:2311.04656

    arXiv 2023

Show all 42 references
  1. [9]

    Local complementation and interlacement graphs

    Hubert de Fraysseix. Local complementation and interlacement graphs. Discrete Math. , 33(1):29--35, 1981. https://doi.org/10.1016/0012-365X(81)90255-7 doi:10.1016/0012-365X(81)90255-7

    1981 doi

  2. [10]

    Erd o s- P \' o sa property of cycles that are far apart

    Vida Dujmović, Gwenaël Joret, Piotr Micek, and Pat Morin. Erd o s- P \' o sa property of cycles that are far apart. preprint, 2025. https://arxiv.org/abs/2412.13893 arXiv:2412.13893

    2025 arXiv

  3. [11]

    On independent circuits contained in a graph

    Paul Erd o s and Lajos P \'o sa. On independent circuits contained in a graph. Canad. J. Math. , 17:347--352, 1965. https://doi.org/10.4153/CJM-1965-035-8 doi:10.4153/CJM-1965-035-8

    1965 doi

  4. [12]

    Fon-Der-Flaass

    Dmitri G. Fon-Der-Flaass. On local complementations of graphs. In Combinatorics (Eger, 1987) , volume 52 of Colloq. Math. Soc. J\'anos Bolyai , pages 257--266. North-Holland, Amsterdam, 1988

    1987

  5. [13]

    James F. Geelen. A generalization of T utte's characterization of totally unimodular matrices. J. Combin. Theory Ser. B , 70(1):101--117, 1997. https://doi.org/10.1006/jctb.1997.1751 doi:10.1006/jctb.1997.1751

    1997

  6. [14]

    Geelen, A

    James F. Geelen, A. M. H. Gerards, and Geoff Whittle. Branch-width and well-quasi-ordering in matroids and graphs. J. Combin. Theory Ser. B , 84(2):270--290, 2002. https://doi.org/10.1006/jctb.2001.2082 doi:10.1006/jctb.2001.2082

    2002

  7. [15]

    Geelen, A

    James F. Geelen, A. M. H. Gerards, and Geoff Whittle. Disjoint cocircuits in matroids with large rank. J. Combin. Theory Ser. B , 87(2):270--279, 2003. https://doi.org/10.1016/S0095-8956(02)00010-2 doi:10.1016/S0095-8956(02)00010-2

    2003 doi

  8. [16]

    Excluding a planar graph from GF (q) -representable matroids

    Jim Geelen, Bert Gerards, and Geoff Whittle. Excluding a planar graph from GF (q) -representable matroids. J. Combin. Theory Ser. B , 97(6):971--998, 2007. https://doi.org/10.1016/j.jctb.2007.02.005 doi:10.1016/j.jctb.2007.02.005

    2007 doi

  9. [17]

    The highly connected matroids in minor-closed classes

    Jim Geelen, Bert Gerards, and Geoff Whittle. The highly connected matroids in minor-closed classes. Ann. Comb. , 19(1):107--123, 2015. https://doi.org/10.1007/s00026-015-0251-3 doi:10.1007/s00026-015-0251-3

    2015 doi

  10. [18]

    The E rd o s- P \'o sa property for matroid circuits

    Jim Geelen and Kasper Kabell. The E rd o s- P \'o sa property for matroid circuits. J. Combin. Theory Ser. B , 99(2):407--419, 2009. https://doi.org/10.1016/j.jctb.2008.08.004 doi:10.1016/j.jctb.2008.08.004

    2009 doi

  11. [19]

    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. https://doi.org/10.1016/j.jctb.2020.08.004 doi:10.1016/j.jctb.2020.08.004

    2023 doi

  12. [20]

    Flipper games for monadically stable graph classes

    Jakub Gajarsk \'y , Nikolas M\"ahlmann, Rose McCarty, Pierre Ohlmann, Micha Pilipczuk, Wojciech Przybyszewski, Sebastian Siebertz, Marek Soko owski, and Szymon Toru\'nczyk. Flipper games for monadically stable graph classes. In 50th I nternational C olloquium on A utomata, L a...

    2023 doi

  13. [21]

    Circle graph obstructions under pivoting

    Jim Geelen and Sang - il Oum. Circle graph obstructions under pivoting. J. Graph Theory , 61(1):1--11, 2009. https://doi.org/10.1002/jgt.20363 doi:10.1002/jgt.20363

    2009 doi

  14. [22]

    Algebraic graph theory , volume 207 of Graduate Texts in Mathematics

    Chris Godsil and Gordon Royle. Algebraic graph theory , volume 207 of Graduate Texts in Mathematics . Springer-Verlag, New York, 2001. https://doi.org/10.1007/978-1-4613-0163-9 doi:10.1007/978-1-4613-0163-9

    2001 doi

  15. [23]

    Kevin Grace and Stefan H. M. van Zwam. On perturbations of highly connected dyadic matroids. Ann. Comb. , 22(3):513--542, 2018. https://doi.org/10.1007/s00026-018-0396-y doi:10.1007/s00026-018-0396-y

    2018 doi

  16. [24]

    Packing and covering immersions in 4 -edge-connected graphs

    Chun-Hung Liu. Packing and covering immersions in 4 -edge-connected graphs. J. Combin. Theory Ser. B , 151:148--222, 2021. https://doi.org/10.1016/j.jctb.2021.06.005 doi:10.1016/j.jctb.2021.06.005

    2021 doi

  17. [25]

    Local structure for vertex-minors

    Rose McCarty. Local structure for vertex-minors. P h D thesis, University of Waterloo , Oct 2021. URL: https://uwspace.uwaterloo.ca/handle/10012/17633

    2021

  18. [26]

    Delta-matroids for graph theorists

    Iain Moffatt. Delta-matroids for graph theorists. In Surveys in combinatorics 2019 , volume 456 of London Math. Soc. Lecture Note Ser. , pages 167--220. Cambridge Univ. Press, Cambridge, 2019. https://doi.org/10.1017/9781108649094.007 doi:10.1017/9781108649094.007

    2019 doi

  19. [27]

    The average cut-rank of graphs

    Huy-Tung Nguyen and Sang - il Oum. The average cut-rank of graphs. European J. Combin. , 90:103183, 22, 2020. https://doi.org/10.1016/j.ejc.2020.103183 doi:10.1016/j.ejc.2020.103183

    2020

  20. [28]

    Approximating clique-width and branch-width

    Sang - il Oum and Paul Seymour. Approximating clique-width and branch-width. J. Combin. Theory Ser. B , 96(4):514--528, 2006. https://doi.org/10.1016/j.jctb.2005.10.006 doi:10.1016/j.jctb.2005.10.006

    2006 doi

  21. [29]

    Rank-width and vertex-minors

    Sang - il Oum. Rank-width and vertex-minors. J. Combin. Theory Ser. B , 95(1):79--100, 2005. https://doi.org/10.1016/j.jctb.2005.03.003 doi:10.1016/j.jctb.2005.03.003

    2005 doi

  22. [30]

    Rank-width and well-quasi-ordering

    Sang - il Oum. Rank-width and well-quasi-ordering. SIAM J. Discrete Math. , 22(2):666--682, 2008. https://doi.org/10.1137/050629616 doi:10.1137/050629616

    2008 doi

  23. [31]

    Excluding a bipartite circle graph from line graphs

    Sang - il Oum. Excluding a bipartite circle graph from line graphs. J. Graph Theory , 60(3):183--203, 2009. https://doi.org/10.1002/jgt.20353 doi:10.1002/jgt.20353

    2009 doi

  24. [32]

    Rank-width: algorithmic and structural results

    Sang - il Oum. Rank-width: algorithmic and structural results. Discrete Appl. Math. , 231:15--24, 2017. https://doi.org/10.1016/j.dam.2016.08.006 doi:10.1016/j.dam.2016.08.006

    2017 doi

  25. [33]

    Graph classes through the lens of logic

    Michał Pilipczuk. Graph classes through the lens of logic. preprint, 2025. https://arxiv.org/abs/2501.04166 arXiv:2501.04166

    2025 arXiv

  26. [34]

    Dynamic Erd o s-P\'osa listing

    Jean-Florent Raymond. Dynamic Erd o s-P\'osa listing. https://perso.ens-lyon.fr/jean-florent.raymond/Erd accessed April 2025

    2025

  27. [35]

    Reed, Neil Robertson, Paul Seymour, and Robin Thomas

    Bruce A. Reed, Neil Robertson, Paul Seymour, and Robin Thomas. Packing directed circuits. Combinatorica , 16(4):535--554, 1996. https://doi.org/10.1007/BF01271272 doi:10.1007/BF01271272

    1996 doi

  28. [36]

    Graph minors

    Neil Robertson and Paul Seymour. Graph minors. V . E xcluding a planar graph. J. Combin. Theory Ser. B , 41(1):92--114, 1986. https://doi.org/10.1016/0095-8956(86)90030-4 doi:10.1016/0095-8956(86)90030-4

    1986 doi

  29. [37]

    Reed and F

    Bruce A. Reed and F. Bruce Shepherd. The G allai- Y ounger conjecture for planar graphs. Combinatorica , 16(4):555--566, 1996. https://doi.org/10.1007/BF01271273 doi:10.1007/BF01271273

    1996 doi

  30. [38]

    Neil Robertson and P. D. Seymour. Graph minors. XX . W agner's conjecture. J. Combin. Theory Ser. B , 92(2):325--357, 2004. https://doi.org/10.1016/j.jctb.2004.08.001 doi:10.1016/j.jctb.2004.08.001

    2004 doi

  31. [39]

    A new proof and generalizations of a theorem of Erd o s and P\'osa on graphs without \(k+1\) independent circuits

    Mikl\' o s Simonovits. A new proof and generalizations of a theorem of Erd o s and P\'osa on graphs without \(k+1\) independent circuits. Acta Math. Acad. Sci. Hung. , 18:191--206, 1967. https://doi.org/10.1007/BF02020974 doi:10.1007/BF02020974

    1967 doi

  32. [40]

    On the presence of disjoint subgraphs of a specified type

    Carsten Thomassen. On the presence of disjoint subgraphs of a specified type. J. Graph Theory , 12(1):101--111, 1988. https://doi.org/10.1002/jgt.3190120111 doi:10.1002/jgt.3190120111

    1988 doi

  33. [41]

    Flip-width: cops and robber on dense graphs

    Szymon Toru\'nczyk. Flip-width: cops and robber on dense graphs. In 2023 IEEE 64th A nnual S ymposium on F oundations of C omputer S cience--- FOCS 2023 , pages 663--700. IEEE Computer Soc., Los Alamitos, CA, [2023] 2023. https://doi.org/10.1109/FOCS57990.2023.00045 doi:10.110...

    2023

  34. [42]

    Graphical description of the action of local clifford transformations on graph states

    Maarten Van den Nest, Jeroen Dehaene, and Bart De Moor. Graphical description of the action of local clifford transformations on graph states. Phys. Rev. A , 69:022316, 2004. https://doi.org/10.1103/PhysRevA.69.022316 doi:10.1103/PhysRevA.69.022316

    2004 doi

Pith tools

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