Pith. sign in

REVIEW 2 major objections 4 minor 1 cited by

Excluding an induced wheel minor in graphs without large induced stars

T0 review · 2 major / 4 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 In $K_{1,d}$-free graphs, excluding a fixed wheel as an induced minor forces bounded tree-independence number, and with it polynomial-time solvability of Maximum Independent Set and of induced-wheel detection.

desk verdict A genuinely useful paper on wheels and tree-independence number; referee it, but require fixes to two proof gaps. read the letter →

arxiv 2506.08829 v1 pith:KWDDMJPA submitted 2025-06-10 math.CO cs.DMcs.DS

Mujin Choi , Claire Hilaire , Martin Milanič , Sebastian Wiederrecht This is my paper · ORCID
classification math.COcs.DMcs.DS MSC 05C7505C8305C6905C85
keywords tree-independencenumberinducedminorwheelgraphsK_{1d}-freestrongbramblesalpha-treedepthMaximumIndependentSettree-decomposition
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper proves that, in graphs with no large induced star, forbidding a fixed wheel as an induced minor forces the whole graph to be tree-like in a sense that tolerates dense subgraphs: the tree-independence number, the maximum independence number of a bag in an optimal tree-decomposition, is bounded by a function of $d$ and $\ell$. Concretely, Theorem 1.1 gives $f_{1.1}(d,\ell)\in O(d\ell(\ell^{10}+2(\max\{d+2,\ell\})^5))$ such that every $K_{1,d}$-free graph $G$ either contains $W_\ell$ as an induced minor or satisfies $\alpha\text{-tw}(G)\le f_{1.1}(d,\ell)$. This is the first infinite family of three-connected planar graphs for which the conjecture of Dallard et al., that excluding a fixed planar induced minor in $K_{1,d}$-free graphs bounds tree-independence number, is verified. The payoff is algorithmic: on such graph classes, Maximum Independent Set becomes polynomial-time solvable, and for fixed $d,\ell$ an induced $W_\ell$ minor can be found or ruled out in polynomial time.

What carries the argument

The load-bearing mechanism is the strong-bramble duality (Theorem 1.3), a new approximate min-max relation for tree-independence number. A strong bramble is a collection of connected vertex sets that pairwise intersect; its $\alpha$-order is the minimum independence number of a set that hits every member. Given a $K_{1,d}$-free graph with no $W_\ell$ induced minor, Lemma 6.2 converts a long induced cycle into a tree-decomposition whose internal bags and edge intersections have independence number bounded by $f_{6.2}(d,\ell)$, with leaves carrying the components of $G-N[C]$. Theorem 1.5 guarantees such a long cycle exists whenever a strong bramble has large $\alpha$-order, and the orientation argument in the proof of Theorem 1.1 forces the bramble's cover onto one small bag, contradicting the bramble's order.

What would settle it

Find a $K_{1,d}$-free graph $G$ with no induced $W_\ell$ minor and with $\alpha\text{-tw}(G)$ larger than the bound $f_{1.1}(d,\ell)$; that would refute Theorem 1.1 as stated. A more local test is to determine whether the $\ell\times\ell$ grid really has $W_\ell$ as an induced minor for every $\ell\ge 3$, since a counterexample for some $\ell$ would invalidate the specific reduction in Lemma 6.2.

Watch

Extended reading notes

Core claim

The central claim is that wheels are a sufficient induced-minor obstruction to large tree-independence number inside $K_{1,d}$-free graphs. The proof runs through a new dual object: a strong bramble, a family of pairwise intersecting connected vertex sets, equipped with an $\alpha$-order, the smallest independence number of a vertex set meeting every member. Theorem 1.3 gives an approximate duality: a strong bramble of $\alpha$-order $k$ forces $\alpha\text{-tw}(G)\ge k$, and $\alpha\text{-tw}(G)\ge 4k-2$ forces a strong bramble of $\alpha$-order at least $k$. In a $K_{1,d}$-free graph, a strong bramble of large $\alpha$-order yields a long induced cycle whose closed neighbourhood meets every bramble member (Theorem 1.5), and such a cycle is the scaffold from which a wheel minor is built or a low-width decomposition is extracted via Lemma 6.2.

Load-bearing premise

The argument leans on the assertion, used after applying the grid theorem in Lemma 6.2, that an $\ell\times\ell$ grid contains $W_\ell$ as an induced minor; this containment is plausible but not proved in the text, and if it failed for some $\ell$, the bounded-width decomposition used to prove Theorem 1.1 would not go through.

Editorial extensions

If this is right

  • For every fixed $d\ge 1$ and $\ell\ge 3$, Maximum Weight Independent Set is solvable in polynomial time on $K_{1,d}$-free graphs that exclude $W_\ell$ as an induced minor.
  • For fixed $d$ and $\ell$, the induced $W_\ell$ minor containment problem on $K_{1,d}$-free graphs is polynomial-time solvable: the algorithm either outputs an induced minor model or correctly reports that none exists.
  • Wheels form the first infinite family of three-connected planar graphs whose exclusion as induced minors bounds tree-independence number in $K_{1,d}$-free graphs, a concrete step toward the full conjecture for all planar $H$.
  • The $\alpha$-treedepth results imply that $\{K_{1,d},P_k\}$-free graphs admit elimination forests where every root-to-leaf path has bounded independence number, with a matching logarithmic lower bound on the path $P_k$.

Reading between the lines

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

  • If the factor-four gap in Theorem 1.3 can be closed, tree-independence number would acquire an exact bramble min-max theorem, and the same proof strategy could then apply to other planar $H$ in the conjecture.
  • A direct proof that every $\ell\times\ell$ grid has $W_\ell$ as an induced minor would make Lemma 6.2 fully self-contained; checking this containment is a natural follow-up for anyone relying on the exact function $f_{1.1}$.
  • The introduction of $\alpha$-treedepth suggests a new parameterized-algorithms direction: problems whose running time improves when treedepth is replaced by $\alpha$-treedepth on dense graphs, as Question 8.4 in the paper asks.
  • The polynomial-time detection algorithm inherits its exponent from the approximation algorithm for tree-independence number, so any tightening of that approximation or of $f_{1.1}$ would directly speed up wheel detection in practice.
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. This paper studies the tree-independence number of K_{1,d}-free graphs that exclude a wheel W_ℓ as an induced minor. The main theorem (Theorem 1.1) gives an explicit function f_{1.1}(d,ℓ) such that every K_{1,d}-free graph G either contains W_ℓ as an induced minor or satisfies α-tw(G) ≤ f_{1.1}(d,ℓ). The proof introduces a notion of strong brambles with an α-order and proves an approximate duality with tree-independence number (Theorem 1.3). A dominated-cycle theorem (Theorem 1.5) then produces a long induced cycle covering a large bramble, which is combined with a structural lemma (Lemma 6.2) based on Korhonen's grid theorem to run a contradiction argument. The paper also proves a qualitative strengthening for α-treedepth in {K_{1,d},P_k}-free graphs (Theorem 1.2) and derives polynomial-time algorithms for Maximum Independent Set and for detecting an induced W_ℓ minor in K_{1,d}-free graphs.

Significance. The result is a significant step toward the conjecture of Dallard et al. [19]. It provides the first infinite family of 3-connected planar graphs H for which excluding H as an induced minor bounds α-tw in K_{1,d}-free graphs. The paper introduces a useful bramble-type duality for tree-independence number and gives fully explicit, parameter-free bounds. The algorithmic consequences for MWIS and W_ℓ-Induced Minor Containment are valuable. However, two proof gaps in the current version (in Theorem 4.2 and Lemma 6.2) need to be repaired before the main claims can be regarded as established.

major comments (2)
  1. [§4, Theorem 4.2, Case 2] In the construction of the refined tree-decomposition, the set S′ is defined as S∩β(ℓ)∩β(t). Any vertex of S that lies in β(ℓ) but not in β(t) appears only in the bag of the leaf ℓ in the old decomposition (because ℓ is a leaf). After the old leaf ℓ is removed, such a vertex is not contained in any of the new bags: it is not in any R_i (since R_i⊆V(C_i) and the components C_i exclude S), not in S′, and not in β(t). Hence the union of the bags of (T′,β′) fails to cover V(G), so (T′,β′) is not a tree-decomposition. Since Theorem 1.3 relies on this construction, this is a load-bearing gap. A simple replacement of S′ by S throughout Case 2 repairs the coverage, but the authors must also verify condition (iii) of the definition of a tree-decomposition for vertices of S that were only in β(ℓ); with S′ replaced by S these vertices appear in several new bags whose induced subtree is not automatically connected.
  2. [§6, Lemma 6.2] Two assertions in the proof of Lemma 6.2 are not justified. First, after applying Korhonen's theorem (Theorem 1.6) it is stated that an (ℓ×ℓ)-grid contains W_ℓ as an induced minor; this containment is plausible but needs a proof (for example by partitioning the outer cycle into ℓ connected parts and contracting the interior to the hub). Second, the construction of the leaf t_J for a component J of G−N[C] requires a vertex t∈V(T′) with N(J)⊆β_3(t). The text justifies this by Observation 1, but Observation 1 only guarantees that if a bag contains some vertex of the component K of G−C that contains J, then it contains N(C)∩V(K); it does not guarantee that the cycle-side neighbours N(K)⊆V(C) belong to the same bag. Without such a bag, attaching t_J at a single vertex does not yield a valid tree-decomposition. This gap affects the main structural lemma on which Theorem 1.1 rests.
minor comments (4)
  1. [§7.4 (Theorem 7.4)] The inequality α-tw(G−v) ≥ α-tw(G)−1 used in the iteration is not stated; it follows by adding v to every bag of an optimal decomposition of G−v, but it should be made explicit.
  2. [§1.1] The sentence 'there exist a 3-connected planar graph H on k vertices' is imprecise; the wheel W_{k−1} has exactly k vertices, so the statement should read 'for every integer k≥4 there is a 3-connected planar graph H on k vertices, namely W_{k−1}.'
  3. [§5 (Theorem 5.2)] In the sentence 'Note that R is an induced path, unless P has length 1', it would help to spell out that when P has length 1 the union C=P∪R is still an induced cycle, since R has no internal vertex with neighbours in P other than s and t.
  4. [§3 (Theorem 1.2(i))] The formula α-td(P_k)=⌈log(k/3+1)⌉ for k=1,2 gives 1, matching the definition; the proof of the lower bound could mention that the base cases k∈[3] are immediate.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the derivation is self-contained, with external theorems (Korhonen, Ramsey, Courcelle) carrying the load; self-citations are contextual or independent.

full rationale

I walked the claimed derivation chain: Theorem 1.3 is proved from Theorem 4.2 and Lemma 4.3, both constructed in the paper; Theorem 1.5 follows from Lemma 5.1 and Theorem 5.2 plus the K_{1,d}-free degree bound; Lemma 6.2 invokes Korhonen's theorem (Theorem 1.6) as an external input and then combines it with the paper's own wheel-exclusion argument; and Theorem 1.1 assembles these pieces with explicit functions and no fitted parameters. No equation equates an input to an output by construction, and no parameter is fitted to data and then renamed a prediction. The self-citations appearing in the paper are not load-bearing in a circular sense: Conjecture 1.7 from [19] is motivation, not an assumption; the strengthening in Theorem 1.2 is proved directly by induction; the approximation algorithm [18] and the CMSO2 optimization theorem [26] are independent external results whose assumptions do not include the wheel-minor conclusion. Two non-circular correctness caveats should be weighed separately: first, Lemma 6.2 asserts 'This implies that G contains W_ℓ as an induced minor' immediately after applying Korhonen's grid theorem, but the needed fact that an ℓ×ℓ grid contains W_ℓ as an induced minor is not proved in the text; second, the skeptical reader's concern about Theorem 4.2 is a genuine proof gap: in Case 2 the definition S′ := S ∩ β(ℓ) ∩ β(t) can omit vertices of S lying outside β(t), so the displayed construction may fail to cover the graph, though replacing S′ by S appears to repair it locally. These are correctness risks, not circular reductions, and do not affect the circularity score.

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

No free parameters are fitted; all bounds are explicit. The paper introduces new mathematical objects (strong brambles, α-treedepth) but they are fully defined and proved, so they do not act as unexplained postulated entities. The load-bearing imported results are external theorems; the only implicit assumption is the grid-to-wheel containment step.

assumptions (5)
  • standard math Standard graph-theoretic toolkit: tree-decomposition axioms, connected components, Ramsey's theorem, Courcelle's theorem.
    Used throughout the paper; definitions appear in Section 2 and the metatheorems in Section 7.
  • standard math Korhonen's grid induced minor theorem (Theorem 1.6): bounded-degree graphs of large treewidth contain large grids as induced minors.
    Used in Lemma 6.2 to force a grid in G1 and thereby a wheel in G.
  • standard math Approximation algorithm of Dallard et al. [18] for tree-independence number.
    Used in Theorem 7.4 to obtain a tree-decomposition of bounded α-width or a large-α-tw certificate.
  • standard math Lima et al. metatheorem (Theorem 7.2) for CMSO2 optimization on graphs of bounded tree-independence number.
    Used in the proof of Theorem 7.1 to find small induced minor models.
  • domain assumption An ℓ×ℓ grid contains W_ℓ as an induced minor.
    Invoked without proof in Lemma 6.2 in the sentence 'This implies that G contains Wℓ as an induced minor'; this is the main implicit assumption flagged in the review.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Excluding an induced wheel minor in graphs without large induced stars." pith.science (2026). https://pith.science/paper/KWDDMJPA

@misc{pith2026250608829,
  author       = {Pith},
  title        = {Pith review of: Excluding an induced wheel minor in graphs without large induced stars},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/KWDDMJPA}},
  note         = {Machine review of arXiv:2506.08829}
}
abstract

We study a conjecture due to Dallard, Krnc, Kwon, Milani\v{c}, Munaro, \v{S}torgel, and Wiederrecht stating that for any positive integer $d$ and any planar graph $H$, the class of all $K_{1,d}$-free graphs without $H$ as an induced minor has bounded tree-independence number. A $k$-wheel is the graph obtained from a cycle of length $k$ by adding a vertex adjacent to all vertices of the cycle. We show that the conjecture of Dallard et al. is true when $H$ is a $k$-wheel for any $k\geq 3$. Our proof uses a generalization of the concept of brambles to tree-independence number. As a consequence of our main result, several important $\mathsf{NP}$-hard problems such as Maximum Independent Set are tractable on $K_{1,d}$-free graphs without large induced wheel minors. Moreover, for fixed $d$ and $k$, we provide a polynomial-time algorithm that, given a $K_{1,d}$-free graph $G$ as input, finds an induced minor model of a $k$-wheel in $G$ if one exists.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

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

  1. Excluding a Ladder as an Induced Minor in Graphs Without Induced Stars

    math.CO 2025-09 conditional novelty 7.0 of 10

    Every K_{1,d}-free graph that excludes the k-ladder as an induced minor has tree-independence number bounded by a function of k and d.

Reference graph

Works this paper leans on

37 extracted references · 14 canonical work pages · cited by 1 Pith paper

  1. [19]

    Dallard, C., Krnc, M., Kwon, O., Milanič, M., Munaro, A., Štorgel, K., Wiederrecht, S.: Treewidth versus clique number. IV. Tree-independence number of graphs excluding an induced star (2024),https://arxiv.org/abs/2402.11222

    arXiv 2024

  2. [1]

    Freiburg im Breisgau: Univ

    Adler, I.: Width functions for hypertree decompositions. Freiburg im Breisgau: Univ. Freiburg, Fakultät für Mathematik und Physik (Dissertation) (2006),d-nb.info/979896851

    arXiv 2006

  3. [2]

    In: Azar, Y., Panigrahi, D

    Ahn, J., Gollin, J.P., Huynh, T., Kwon, O.: A coarse Erdős-Pósa theorem. In: Azar, Y., Panigrahi, D. (eds.) Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025, New Orleans, LA, USA, January 12-15, 2025. pp. 3363–3381. SIAM (2025),https://doi.org/10.1137/1.9781611978322.109

    work page doi:10.1137/1.9781611978322.109 2025

  4. [3]

    Induced subgraphs and tree decompositions XIII. Basic obstructions in $\mathcal{H}$-free graphs for finite $\mathcal{H}$

    Alecu, B., Chudnovsky, M., Hajebi, S., Spirkl, S.: Induced subgraphs and tree decompositions XIII. Basic obstructions inH-free graphs for finiteH (2023), https://arxiv.org/abs/ 2311.05066

    work page Pith review arXiv 2023

  5. [4]

    Belmonte, R., Kim, E.J., Lampis, M., Mitsou, V., Otachi, Y.: Grundy distinguishes treewidth from pathwidth. SIAM J. Discrete Math.36(3), 1761–1787 (2022),https://doi.org/10. 1137/20M1385779

    work page 2022

  6. [5]

    Manuscript in preparation

    Bešter Štorgel, K., Dallard, C., Lozin, V., Milanič, M., Zamaraev, V.: Awesome graph parameters. Manuscript in preparation

    work page

  7. [6]

    Błasiok, J., Kamiński, M., Raymond, J.F., Trunck, T.: Induced minors and well-quasi- ordering. J. Combin. Theory Ser. B134, 110–142 (2019),https://doi.org/10.1016/j. jctb.2018.05.005

    doi:10.1016/j 2019

  8. [7]

    Bonnet, E., Kim, E.J., Thomassé, S., Watrigant, R.: Twin-width I: Tractable FO model checking. J. ACM69(1) (2021),https://doi.org/10.1145/3486655

    doi:10.1145/3486655 2021

Show all 37 references
  1. [8]

    Bousquet, N., Dallard, C., Dumas, M., Hilaire, C., Milanič, M., Perez, A., Trotignon, N.: Induced Minor Models. I. Structural Properties and Algorithmic Consequences (2025), https://arxiv.org/abs/2402.08332

    2025 arXiv

  2. [9]

    Walls and claws (2025),https://arxiv.org/abs/2501.14658

    Chudnovsky, M., Codsi, J., Lokshtanov, D., Milanič, M., Sivashankar, V.: Tree independence number V. Walls and claws (2025),https://arxiv.org/abs/2501.14658

    2025 arXiv

  3. [10]

    Thetas, prisms and stars (2024),https://arxiv.org/abs/2406.13053

    Chudnovsky, M., Hajebi, S., Trotignon, N.: Tree independence number III. Thetas, prisms and stars (2024),https://arxiv.org/abs/2406.13053

    2024

  4. [11]

    Chuzhoy, J., Tan, Z.: Towards tight(er) bounds for the excluded grid theorem. J. Combin. Theory Ser. B146, 219–265 (2021),https://doi.org/10.1016/j.jctb.2020.09.010

    2021 doi

  5. [12]

    Courcelle, B.: The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Information and Computation85(1), 12–75 (1990),https://doi.org/10.1016/ 0890-5401(90)90043-H

    1990

  6. [13]

    Courcelle, B., Engelfriet, J.: Graph structure and monadic second-order logic: a language- theoretic approach, vol. 138. Cambridge University Press (2012) 25

    2012

  7. [14]

    Discrete Applied Mathematics101(1), 77–114 (2000), https://doi.org/10.1016/S0166-218X(99)00184-5

    Courcelle, B., Olariu, S.: Upper bounds to the clique width of graphs. Discrete Applied Mathematics101(1), 77–114 (2000), https://doi.org/10.1016/S0166-218X(99)00184-5

    2000 doi

  8. [15]

    Dallard, C., Milanič, M., Štorgel, K.: Treewidth versus clique number. III. Tree-independence number of graphs with a forbidden structure. Journal of Combinatorial Theory, Series B 167, 338–391 (2024),https://doi.org/10.1016/j.jctb.2024.03.005

    2024 doi

  9. [16]

    Dallard, C., Milanič, M., Štorgel, K.: Treewidth versus clique number. I. Graph classes with a forbidden structure. SIAM Journal on Discrete Mathematics35(4), 2618–2646 (2021), https://doi.org/10.1137/20M1352119

    2021 doi

  10. [17]

    Dallard, C., Milanič, M., Štorgel, K.: Treewidth versus clique number. II. Tree-independence number. Journal of Combinatorial Theory, Series B164, 404–442 (2024),https://doi. org/10.1016/j.jctb.2023.10.006

    2024 doi

  11. [18]

    In: Bringmann, K., Grohe, M., Puppis, G., Svensson, O

    Dallard, C., Fomin, F.V., Golovach, P.A., Korhonen, T., Milanič, M.: Computing tree decompositions with small independence number. In: Bringmann, K., Grohe, M., Puppis, G., Svensson, O. (eds.) 51st International Colloquium on Automata, Languages, and Programming, ICALP 2024, J...

    2024

  12. [20]

    Diestel, R.: Graph theory, Graduate Texts in Mathematics, vol. 173. Springer, Berlin, sixth edn. (2025)

    2025

  13. [21]

    Algorithmica13(3), 266–282 (1995),https://doi.org/10

    Fellows, M.R., Kratochvíl, J., Middendorf, M., Pfeiffer, F.: The complexity of induced minors and related problems. Algorithmica13(3), 266–282 (1995),https://doi.org/10. 1007/BF01190507

    1995

  14. [22]

    Gyárfás, A.: Problems from the world surrounding perfect graphs. Zastos. Mat.19(3-4), 413–441 (1987),https://doi.org/10.4064/am-19-3-4-413-441

    1987 doi

  15. [23]

    Hilaire, C., Milanič, M., Trotignon, N., Vasić, Ð.: Treewidth versus clique number: induced minors (2024),https://arxiv.org/abs/2410.17979

    2024 arXiv

  16. [24]

    Korhonen, T.: Grid induced minor theorem for graphs of small degree. J. Combin. Theory Ser. B160, 206–214 (2023),https://doi.org/10.1016/j.jctb.2023.01.002

    2023 doi

  17. [25]

    In: Woodruff, D.P

    Korhonen, T., Lokshtanov, D.: Induced-minor-free graphs: Separator theorem, subexponen- tial algorithms, and improved hardness of recognition. In: Woodruff, D.P. (ed.) Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, VA, USA, January 7-...

    2024 doi

  18. [26]

    In: Chan, T.M., Fischer, J., Iacono, J., Herman, G

    Lima, P.T., Milanič, M., Muršič, P., Okrasa, K., Rzążewski, P., Štorgel, K.: Tree de- compositions meet induced matchings: Beyond max weight independent set. In: Chan, T.M., Fischer, J., Iacono, J., Herman, G. (eds.) 32nd Annual European Symposium on Algorithms, ESA 2024, Sept...

    2024 doi

  19. [27]

    Matoušek, J., Nešetřil, J., Thomas, R.: On polynomial time decidability of induced-minor- closed classes. Comment. Math. Univ. Carolin.29(4), 703–710 (1988),http://eudml.org/ doc/17683

    1988

  20. [28]

    European J

    Ne˘ set˘ ril, J., Ossona de Mendez, P.: Tree-depth, subgraph coloring and homomorphism bounds. European J. Combin.27(6), 1022–1041 (2006),https://doi.org/10.1016/j.ejc. 2005.01.010

    2006 doi

  21. [29]

    Journal of Combina- torial Theory, Series B96(4), 514–528 (2006),https://doi.org/10.1016/j.jctb.2005

    Oum, S., Seymour, P.: Approximating clique-width and branch-width. Journal of Combina- torial Theory, Series B96(4), 514–528 (2006),https://doi.org/10.1016/j.jctb.2005. 10.006

    2006 doi

  22. [30]

    Ramsey, F.P.: On a Problem of Formal Logic. Proc. London Math. Soc. (2)30(4), 264–286 (1929),https://doi.org/10.1112/plms/s2-30.1.264

    1929 doi

  23. [31]

    European J

    Reed, B., Wood, D.: Polynomial treewidth forces a large grid-like-minor. European J. Combin.33(3), 374–379 (2012),https://doi.org/10.1016/j.ejc.2011.09.004

    2012 doi

  24. [32]

    Robertson, N., Seymour, P.: Graph minors. V. Excluding a planar graph. J. Combin. Theory Ser. B41, 92–114 (1986),https://doi.org/10.1016/0095-8956(86)90030-4

    1986 doi

  25. [33]

    Robertson, N., Seymour, P.: Graph minors. IV. Tree-width and well-quasi-ordering. Journal of Combinatorial Theory, Series B48(2), 227–254 (1990),https://doi.org/10.1016/0095- 8956(90)90120-O

    1990 doi

  26. [34]

    Robertson, N., Seymour, P., Thomas, R.: Quickly excluding a planar graph. J. Combin. Theory Ser. B62(2), 323–348 (1994),https://doi.org/10.1006/jctb.1994.1073

    1994

  27. [35]

    Seymour, P.: Tree-chromatic number. J. Combin. Theory Ser. B116, 229–237 (2016), https://doi.org/10.1016/j.jctb.2015.08.002

    2016 doi

  28. [36]

    Discrete Appl

    Yan, J.H., Chen, J.J., Chang, G.J.: Quasi-threshold graphs. Discrete Appl. Math.69(3), 247–255 (1996),https://doi.org/10.1016/0166-218X(96)00094-7

    1996 doi

  29. [37]

    In: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms

    Yolov, N.: Minor-matching hypertree width. In: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms. pp. 219–233. SIAM (2018),https://doi. org/10.1137/1.9781611975031.16 27

    2018 doi

Pith tools

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