Tree independence number V. Walls and claws

Daniel Lokshtanov; Julien Codsi; Maria Chudnovsky; Martin Milani\v{c}; Varun Sivashankar

REVIEW 3 major objections 3 minor 2 cited by

Tree independence number V. Walls and claws

T0 review · 3 major / 3 minor · reviewed 2026-08-10 · deepseek-v4-flash

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

Pith's one-line read Every $n$-vertex graph with no induced line graph of a wall subdivision, no induced subdivided claw $S_{t,t,t}$, and no induced $K_{t,t}$ has tree independence number at most $c(t)\log^4 n$.

desk verdict New polylog tree-independence bound for walls-and-claws-free graphs; proof is deep and mostly sound, with a repairable typo and one imported lemma that deserves a closer look. read the letter →

arxiv 2501.14658 v2 pith:GEYUARCA submitted 2025-01-24 math.CO cs.DMcs.DS

Maria Chudnovsky , Julien Codsi , Daniel Lokshtanov , Martin Milanič , Varun Sivashankar This is my paper · ORCID

classification math.COcs.DMcs.DS MSC 05C6905C7505C85

keywords treeindependencenumberwallssubdividedclawsK_{tt}-freegraphsbalancedseparatorsextendedstripdecompositionsmaximumweightindependentsetquasi-polynomialalgorithm

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 establishes a new polylogarithmic bound on a graph width parameter. For every fixed $t$, every $n$-vertex graph with no induced subgraph from the family $\mathcal{L}_t$ (line graphs of subdivisions of the $t\times t$ wall), no induced subdivided claw $S_{t,t,t}$, and no induced $K_{t,t}$ has tree independence number at most $c(t)\log^4 n$. Such a bound matters because graphs of polylogarithmic tree independence number admit quasi-polynomial algorithms for Maximum Weight Independent Set and related NP-hard problems. Along the way, the paper proves that even without the $K_{t,t}$ assumption, these graphs admit balanced separators whose closed neighborhoods are controlled by a bounded number of vertices. This supports a broader conjecture that excluding induced walls should force small tree independence number.

What carries the argument

An extended strip decomposition of $(G,Z)$ with pattern $H$ is the main structural lens: it presents $G$ as a 'fat' line graph over a host graph $H$, with vertices of $G$ distributed over edges, vertices, and triangles of $H$, and adjacency following incidences in $H$. The paper uses the theorem that a set $Z$ is constricted (every tree meets $Z$ at most twice) if and only if such a faithful decomposition exists. Within an induced path $P$, a 'hat' is a vertex outside $P$ adjacent to exactly two consecutive vertices of $P$; hats detect where large-weight components hang off $P$, and two consecutive hats with opposite orientations produce the required balanced separator with small core. The layered-set argument repeatedly chooses separators while keeping tight control on how many chosen separators cover any one vertex, and the final contradiction is driven by a classification lemma: a large stable set in a connected graph forces an induced subgraph that is a path, a caterpillar, the line graph of a caterpillar, a subdivided star, or the line graph of a subdivided star, each of which is then shown to contain the forbidden $S_{t,t,t}$.

What would settle it

Exhibit a connected graph with a large stable set whose minimal induced subgraph witnessing the stable set is none of the five types listed in Lemma 8.2 (path, caterpillar, line graph of a caterpillar, subdivided star, or line graph of a subdivided star), or exhibit a graph in $\mathcal{M}_t$ whose tree independence number grows faster than $c(t)\log^4 n$; either would break the central claim. A direct check of the imported lemma for the value $h=10Nd$ used in Section 8 is the most economical target.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1.2: for each positive integer $t$ there is $c(t)$ such that every $n$-vertex graph in $\mathcal{M}_t$ has tree independence number at most $c(t)\log^4 n$. The proof first establishes Theorem 1.3, a balanced-separator statement: in every $\mathcal{L}_t\cup\{S_{t,t,t}\}$-free graph, every vertex-weight distribution admits a balanced separator contained in the closed neighborhood of at most $d(t)$ vertices. It then refines these separators to 'boosted' separators, combines many of them through a layered-set counting argument, and finishes by contradiction: if the separator's independence number were too large, a structural classification imported from a companion result would force an induced $S_{t,t,t}$, against the hypothesis.

Load-bearing premise

The final contradiction depends on Lemma 8.2, imported without proof from the companion result [5], which classifies the induced subgraph forced by a large stable set in a connected graph; if that classification is wrong, the proof of the $\log^4 n$ bound does not go through.

Editorial extensions

If this is right

For every fixed $t$, Maximum Weight Independent Set is solvable in quasi-polynomial time on the class $\mathcal{M}_t$, because the $O(\log^4 n)$ tree-independence bound feeds the known polynomial algorithm for bounded tree independence number.
The same quasi-polynomial conclusion applies to the other algorithmic problems known to be tractable on graph classes of bounded tree independence number.
Theorem 1.3 supplies a uniform small-core balanced separator for every weight function on $\mathcal{L}_t\cup\{S_{t,t,t}\}$-free graphs, independently of the number of vertices.
Combining the separator theorem with Lemma 1.7 gives the main $\log^4 n$ bound and thereby an alternative proof of the bounded tree independence number for the $\{K_{1,t},S,L(T)\}$-free classes covered by Theorem 1.6.
The results move the field closer to the conjectured statement that all $\mathcal{L}_t$-free graphs with no induced subdivision of the wall are $d$-breakable.

Reading between the lines

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

The $\log^4$ exponent is probably not optimal; the method collects logarithmic factors from the layered-set bookkeeping and from Ramsey bounds, and a sharper cleaning argument could plausibly reduce the exponent, though the paper does not claim this.
If the companion structural lemma were proved inside this paper's framework, the argument would become self-contained and would likely extend to the full conjecture for forests whose components have at most three leaves.
The hat-based separator analysis of induced paths is a transferable template: it may yield bounded breakability for other pairs consisting of one wall-like and one claw-like forbidden induced subgraph.
The construction of boosted separators appears explicit enough that a careful implementation could produce an actual quasi-polynomial algorithm, although constants and runtime are not optimized here.

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.

Desk Editor's Note

read the letter

Here's the short version: this paper proves a genuinely new theorem — every L_t ∪ {S_t,t,t, K_t,t}-free n-vertex graph has tree independence number O(log^4 n), with the usual quasi-poly MWIS corollary. That's a real step in the wall/claw program, and it doesn't follow from anything previously written down. The d-breakability result for L_t ∪ {S_t,t,t}-free graphs is a nice standalone contribution.

What the paper does well: the high-level reduction is clean. Theorem 1.2 is reduced via Lemma 1.7 to finding balanced separators with polylog independence number, and the paper builds the machinery to get those: extended strip decompositions, the boosted separator construction (Section 7), and the layered-set argument (Section 6). Section 5's lemma controlling large stable sets in neighborhoods is carefully done. This is serious, dense combinatorics, and the authors are honest about what is imported from earlier papers in the series.

Soft spots, in proportion:

- Section 8 has a misindexed union bound: the displayed 1 − 2ε∑_{j=1}^µ j ≥ 1 − εµ² is false. The sum should run to µ−1 (or use C(µ,2)). With the correct index the probability is 1/2 + 1/(2µ), so the argument survives. This is a typo, not a hole.

- Lemma 8.2 is the place I'd worry most. It is a modified version of Theorem 5.2 of the companion preprint [5], and the proof contains a compressed step ("Since S is stable...") that is not fully expanded, especially for caterpillar and line-graph-of-caterpillar cases. The step is plausible — the earlier condition H∩N(Y')=Z(H) forces all S-vertices in H to be leaf-like, so taking a minimal induced subgraph on h of them should preserve the type — but a referee should ask for a fuller proof or a direct citation of [5]. If that lemma failed, Theorem 1.8 and hence Theorem 1.2 would be unsupported. I don't see a concrete failure, but this is the load-bearing import.

The paper does not fit parameters or assume its conclusion; the reliance on [5] and [6] is normal for this series and not circular.

Who it's for: anyone working on induced subgraph obstructions to tree independence number, and algorithmic graph classes. It deserves a serious referee; the companion preprint [5] should probably be checked as part of the review. My recommendation: send it to review, with a request to fix the union-bound typo and to expand or more explicitly outsource the proof of Lemma 8.2.

Referee Report

3 major / 3 minor

Summary. The paper proves that for every positive integer t there is c(t) such that every n-vertex graph avoiding the family L_t (line graphs of subdivisions of the t-by-t wall) as well as induced S_{t,t,t} and K_{t,t} has tree independence number at most c(t) log^4 n. This confirms a variant of a conjecture of Dallard et al. and yields quasi-polynomial algorithms for Maximum Weight Independent Set and related problems on this class. The proof is organized around a new balanced-separator theorem for L_t ∪ {S_{t,t,t}}-free graphs (Theorem 1.3), a layered-set technique that produces families of boosted separators with small cores and small independence number, and a section that combines these separators with a structural lemma about large stable sets to force an induced S_{t,t,t}. Along the way the paper also proves a bounded-core separator statement (Theorem 1.3) and a separator-boosting theorem (Theorem 7.6).

Significance. If the proof is correct, Theorem 1.2 is a substantial advance in the study of tree independence number: it gives the first polylogarithmic bound for this particular forbidden family and, through Theorem 1.3, supports the broader program connecting induced-subgraph obstructions to bounded tree independence number. The layered-set lemma (Theorem 6.1) and the boosting theorem (Theorem 7.6) are likely to be reusable tools for other hereditary classes. The paper is transparent about its dependence on companion papers, and the overall strategy is original and technically rich. I regard the main claims as valuable and worthy of publication provided the issues in Section 8 are repaired.

major comments (3)

[Section 8, proof of Theorem 1.8] The displayed union bound is incorrect: the text claims that the probability that no two of the μ chosen vertices lie in the same component of G''\S_i is at least 1 - 2ε∑_{j=1}^μ j ≥ 1 - εμ². Since ∑_{j=1}^μ j = μ(μ+1)/2, the inequality 2ε∑_{j=1}^μ j ≤ εμ² is false for μ ≥ 2, and with ε = 1/(2μ²) the claimed lower bound becomes non-positive for μ > 1. The intended argument is recoverable because the number of unordered pairs is C(μ,2) = ∑_{j=1}^{μ-1} j, and with that correction the inequality 2ε∑_{j=1}^{μ-1} j ≤ εμ² is valid and yields the stated positive probability. This step produces the stable set S and the index set I that are used in the rest of the proof, so the displayed error must be fixed and the proof rewritten accordingly.
[Lemma 8.2] The proof of Lemma 8.2 contains a compressed and underjustified step. After applying Lemma 8.1 to the graph G' and the set Y, the text asserts: 'Since S is stable, the observation in the previous sentence implies that there exists an induced subgraph H' of H...' with |Y''| = h, H'∩S = Z(H'), and H' of the required type. This does not follow from the previous sentence alone. In particular, when H is the line graph of a caterpillar or the line graph of a subdivided star, a naive truncation of a spine can create new pendant edges in the underlying tree that become new vertices of Z(H') not belonging to S, violating the condition H'∩S = Z(H'). The extraction of H' must be argued in detail, specifying how to choose h vertices of S so that the minimal induced subgraph containing them has exactly those S-vertices as its Z-set. This is a load-bearing step because the rest of the proof of Theorem 1.8 relies on the exact equality H∩S = Z(H).
[Section 8, proof of (26)] In the proof that S is stable, the text states that 'for every i∈{1,...,N}, |{s,t}∩N[Y_i]| ≥ 1', but the property that each component of G''\S_i contains at most one vertex of S was only established for i∈I, where I is a subset of size N/2. The subsequent contradiction still follows if the statement is restricted to I, because then N/2 ≤ 2t, contradicting N = 8t²d for t,d ≥ 1. The authors should correct the quantifier and make the contradiction explicit.

minor comments (3)

[Section 8, Lemma 8.2 proof] The sentence 'it is easy to see that H\Y is a caterpillar...' appears to be a typo, since H is already an induced subgraph of G and contains no vertices of Y; it likely should refer to removing S or to the graph H itself.
[Section 4, proof of Theorem 1.3] In the proof of (6), the expression 'v_i⊆ N(P_i)\N(P_j)' should read 'v_i∈ N(P_i)\N(P_j)'.
[Section 1, proof outline] The outline says the final contradiction uses 'paths P1,...,P_{3d}' and then later 'P,Q,R ∈ {P1,...,P_{3d}}'; this notation is consistent but the number 3d should be checked against the earlier N = 8t²d, since the argument actually uses 3d paths after a pigeonhole step with |Y_j| < d; the constants are not balanced in the exposition and a clarifying sentence would help.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the main theorem is derived from independently stated separator lemmas and external structural theorems.

full rationale

The paper does not define any object in terms of the conclusion it purports to prove, and it does not fit any parameter to the target result and then relabel it as a prediction. Theorem 1.2 is reduced via Lemma 1.7, an established separator-to-tree-decomposition lemma from [6], to Theorem 1.8, which is then proved by a long self-contained chain: Theorem 1.3 uses extended strip decompositions from [8] and the excluded-grid theorem from [9], both external to this work; Sections 5-7 build layered-set and boosted-separator arguments whose auxiliary results (Theorem 5.1, Lemma 5.2, Theorem 6.1, Theorem 7.6, Theorem 7.9) are proved in the paper from explicit hypotheses. The final step in Section 8 depends on Lemma 8.2, whose content is a modified version of Theorem 5.2 of [5]. That theorem is attributed to a companion preprint by overlapping authors, so this is a self-citation, but it is not circular: the cited statement is parameter-free, its hypotheses (a connected graph, a large set Y with G\Y connected and every vertex of Y having a neighbor outside Y) do not include the tree-independence bound or the separator conclusion, and the present paper does not re-derive the target from it by construction. The only substantive concern is the compressed observation inside the proof of Lemma 8.2, which may be a proof gap; a gap is a correctness risk, not a circularity. No equation in the paper is equivalent to its input by definition, and no fitted value is disguised as a prediction. Hence no circular step is present.

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

The proof is existential: constants such as d(t), c(t), N, h, and ε are chosen in the proof to make the inequalities work, not fitted to data. The paper's central claim rests on a set of external theorems, several from the authors' own companion papers ([5], [6], [7]), which are treated as axioms here.

assumptions (6)

standard math Lemma 1.7 of [6]: if every normal weight function admits a (w,c)-balanced separator with independence number at most d, then tree-α(G) ≤ (3-c)/(1-c)d.
Invoked in Section 1.1 to reduce Theorem 1.2 to the separator theorem Theorem 1.8. It is a prior theorem by the same group, cited without proof.
standard math Theorem 3.1 of [9] (polynomial excluded grid theorem): graphs with no subdivision of the t×t wall have treewidth O(t^9 log^{c2}t).
Used in Theorem 3.2 and Lemma 3.3 to bound the treewidth of the pattern graph H in extended strip decompositions of L_t-free graphs.
standard math Theorem 2.1 of [8] (three-in-a-tree): a set Z is constricted iff it admits a faithful extended strip decomposition.
Used in Section 4 to convert the constricted triple {z1,z2,z3} into an extended strip decomposition η_h of G_h.
standard math Lemma 5.3 of [7]: there is an induced path P such that N[P] is a w-balanced separator.
Used at the start of the proof of Theorem 1.3 to obtain the initial path P whose neighborhood is a balanced separator.
standard math Lemma 8.1 (Theorem 5.2 of [5]): given a connected graph and a large set Y with neighbors outside Y, there is an induced subgraph H that is a path, caterpillar, line graph of a caterpillar, subdivided star, or line graph of a subdivided star with prescribed intersection with Y.
Used to prove Lemma 8.2, which is the final structural tool in the proof of Theorem 1.8. It is imported from a companion preprint.
standard math Algorithms from [12] and [24] solve MWIS in polynomial time on graphs of bounded tree independence number.
Used to convert Theorem 1.2 into the quasi-polynomial algorithmic consequence stated in the abstract and introduction.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Tree independence number V. Walls and claws." pith.science (2026). https://pith.science/paper/GEYUARCA

@misc{pith2026250114658,
  author       = {Pith},
  title        = {Pith review of: Tree independence number V. Walls and claws},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/GEYUARCA}},
  note         = {Machine review of arXiv:2501.14658}
}

abstract

Given a family $\mathcal{H}$ of graphs, we say that a graph $G$ is $\mathcal{H}$-free if no induced subgraph of $G$ is isomorphic to a member of $\mathcal{H}$. Let $S_{t,t,t}$ be the graph obtained from $K_{1,3}$ by subdividing each edge $t-1$ times, and let $W_{t\times t}$ be the $t$-by-$t$ hexagonal grid. Let $\mathcal{L}_t$ be the family of all graphs $G$ such that $G$ is the line graph of some subdivision of $W_{t \times t}$. We prove that for every positive integer $t$ there exists $c(t)$ such that every $\mathcal{L}_t \cup \{S_{t,t,t}, K_{t,t}\}$-free $n$-vertex graph admits a tree decomposition in which the maximum size of an independent set in each bag is at most $c(t)\log^4n$. This is a variant of a conjecture of Dallard, Krnc, Kwon, Milani\v{c}, Munaro, \v{S}torgel, and Wiederrecht from 2024. This implies that the Maximum Weight Independent Set problem, as well as many other natural algorithmic problems, that are known to be NP-hard in general, can be solved in quasi-polynomial time if the input graph is $\mathcal{L}_t \cup \{S_{t,t,t},K_{t,t}\}$-free. As part of our proof, we show that for every positive integer $t$ there exists an integer $d$ such that every $\mathcal{L}_t \cup \{S_{t,t,t}\}$-free graph admits a balanced separator that is contained in the neighborhood of at most $d$ vertices.

Figures

Figures reproduced from arXiv: 2501.14658 by the authors.

**Figure 1.** Example of an extended strip decomposition with its pattern (here dash lines represent potential edges). This figure was created by Paweł Rzążewski and we use it with his permission. We need a result of [9]: Theorem 3.1 ([9]). There exist positive integers c1 and c2 such that for every positive integer t, every graph with no subgraph isomorphic to a subdivision of the (t × t)-wall has treewidth at most c1t 9 logc2 t… view at source ↗

**Figure 2.** Example of H′ given an H. Now define a weight function w ′ on H′ . For every v ∈ V (H), let w ′ (v) = w(δ(η(v))), that is, w ′ P (v) = e∈E(H) incident with v w(η(e, v)), and let w ′ (vv) = w(η(v)). For every e ∈ E(H) with ends u, v, let w ′ (ve) = w(η(e) \ (η(e, v) ∪ η(e, u))). For every triangle T of H, let w ′ (vT ) = w(η(T)). For every component D′ of G \ D, let w ′ (vD′) = w(D′ ). Now w ′ is a normal function on… view at source ↗

**Figure 3.** Visualization for (5). Suppose such i, j, ℓ, v exist (see [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗

Figures from the paper (8 more)

**Figure 4.** Figure 4: Visualization of h0 and h1. For all h ∈ H2, we define a subpath P(h) of P as follows: P(h) = pi−2t−1-P-pi+2t+2, where N(h)∩P = {pi , pi+1}. Let H3 = H2 \ N(P(h0)). (7) H3 ̸= ∅. Suppose H3 = ∅. Let Y = Y1 ∪ Y2 ∪ P(h0). Now |Y | < 16t < d and N ∪ N[pk] ⊆ N[Y ], contrary …

**Figure 5.** Figure 5: Visualization of Gh (here dashed lines represent non-edges). (8) {z1, z2, z3} is constricted in Gh. Suppose there is a tree T in Gh such that z1, z2, z3 ∈ V (T). We may choose T minimal with this property; then either T is a subdivision of K1,3 and z1, z2, z3 are leave…

**Figure 6.** Figure 6: Visualization of Q1, Q′ 2 and Q′ 3 (in blue). Let δ(h) be the boundary of A(h) in ηh and let γ(h) = δ(h) ∩ P. (11) |γ(h)| ≤ 9. By Lemma 2.3 there exists ∆ ⊆ Gh with |∆| ≤ 3 such that δ(h) ⊆ N[∆]. Since N(P) ∩ Gh ⊆ H3, for every v ∈ ∆, |N[v] ∩ P| ≤ 3. Consequently, |δ(h…

**Figure 7.** Figure 7: Drawing to keep in mind for the proof of Lemma 7.3. Proof. Let (x, B) be an (X, β)-problematic pair. Let I ⊆ N(x) ∩ N(B) be a stable set of size β (see [PITH_FULL_IMAGE:figures/full_fig_p019_7.png]

**Figure 8.** Figure 8: Visualization of the St,t,t obtained in the proof of (22) [PITH_FULL_IMAGE:figures/full_fig_p019_8.png]

**Figure 9.** Figure 9: Visualization of G \ C in Theorem 7.6. Proof. Let H be the graph with vertex set {Y1, . . . , Y⌈kRN⌉}, with Yi adjacent to Yj for i ̸= j if and only if Yi and Yj are not anticomplete to each other. Since |Yj | < k for all j, the graph H is ⌊kR⌋-degenerate, and therefor…

**Figure 10.** Figure 10: A path, a caterpillar, and the line graph of a caterpillar with X ordered. For each i = 1, . . . , h/2, let Pi be a path in H from x2i−1 to x2i . Let i ∈ {1, . . . , h 2 }. By (27), there is a minimal subpath P ′ i of Pi containing x2i−1 and such that P ′ i ∩ Sj ̸= ∅ …

**Figure 11.** Figure 11: Visualization of the St,t,t obtained to prove (29). By (28) and (29), it follows that H is the line graph of a subdivided star. Then H consists of a clique K = {k1, . . . , kh} and paths P1, . . . , Ph, where Pi is from ki to xi . For every i ∈ {1, . . . , h} let I(i)…

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

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

Excluding an induced wheel minor in graphs without large induced stars
math.CO 2025-06 conditional novelty 8.0 of 10

K_{1,d}-free graphs without an induced wheel minor W_ℓ have tree-independence number bounded by an explicit function of d and ℓ.
Excluding paths and bicliques
math.CO 2026-07 accept novelty 7.0 of 10

For {P_s,K_{t,t}}-free graphs, the maximum path length is at most 2^{ω(G)^c}, and treedepth is clique-polynomial.

Reference graph

Works this paper leans on

24 extracted references · 20 canonical work pages · cited by 2 Pith papers

[5]

Induced subgraphs and tree decompositions XV. Even-hole-free graphs with bounded clique number have logarithmic treewidth

M. Chudnovsky, P. Gartland, S. Hajebi, D. Lokshtanov, and S. Spirkl. Induced subgraphs and tree decompositions XV. Even-hole-free graphs have logarithmic treewidth. Preprint available athttps://arxiv.org/abs/2402.14211, 2024

work page Pith review arXiv 2024
[6]

Chudnovsky, S

M. Chudnovsky, S. Hajebi, D. Lokshtanov, and S. Spirkl. Tree independence number II. Three-path-configurations. Preprint available athttps://arxiv.org/abs/2405.00265, 2024

arXiv 2024
[1]

Induced subgraphs and tree decompositions X. Towards logarithmic treewidth for even-hole-free graphs

T. Abrishami, B. Alecu, M. Chudnovsky, S. Hajebi, and S. Spirkl. Induced subgraphs and tree decompositions X. Towards logarithmic treewidth for even-hole-free graphs. Preprint available athttps://arxiv.org/abs/2307.13684, 2024

work page Pith review arXiv 2024
[2]

J. Ahn, J. P. Gollin, T. Huynh, and O. Kwon. A coarse Erdős-Pósa theorem. Preprint available athttps://arxiv.org/ abs/2407.05883, 2024. Accepted for publication in the proceedings of SODA ’25

arXiv 2024
[3]

H. L. Bodlaender. Dynamic programming on graphs with bounded treewidth. InAutomata, languages and programming (Tampere, 1988), volume 317 ofLecture Notes in Comput. Sci. , pages 105–118. Springer, Berlin, 1988

work page 1988
[4]

Graphs with no long claws: An improved bound for the analog of the Gy\'{a}rf\'{a}s' path argument

R. Bourneuf, J. Masaříková, W. Nadara, and M. Pilipczuk. Graphs with no long claws: An improved bound for the analog of the Gyárfás path argument. Preprint available athttps://arxiv.org/abs/2501.13907, 2025

work page Pith review arXiv 2025
[7]

Chudnovsky, M

M. Chudnovsky, M. Pilipczuk, M. Pilipczuk, and S. Thomassé. Quasi-polynomial time approximation schemes for the maximum weight independent set problem inH-free graphs. SIAM Journal on Computing , 53(1):47–86, 2024

work page 2024
[8]

Chudnovsky and P

M. Chudnovsky and P. Seymour. The three-in-a-tree problem.Combinatorica, 30:387–417, 2010

work page 2010

Show all 24 references

[9]

Chuzhoy and Z

J. Chuzhoy and Z. Tan. Towards tight(er) bounds for the excluded grid theorem.Journal of Combinatorial Theory, Series B, 146:219–265, 2021

2021
[10]

Dallard, F

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

2024
[11]

Dallard, M

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

2024 arXiv
[12]

Dallard, M

C. Dallard, M. Milanič, and K. Štorgel. Treewidth versus clique number. II. Tree-independence number.J. Combin. Theory Ser. B , 164:404–442, 2024

2024
[13]

Dallard, M

C. Dallard, M. Milanič, and K. Štorgel. Treewidth versus clique number. III. Tree-independence number of graphs with a forbidden structure.J. Combin. Theory Ser. B , 167:338–391, 2024

2024
[14]

M. R. Garey and D. S. Johnson. “Strong” NP-completeness results: motivation, examples, and implications.J. Assoc. Comput. Mach., 25(3):499–508, 1978

1978
[15]

Gartland

P. Gartland. Quasi-Polynomial Time Techniques for Independent Set and Beyond in Hereditary Graph Classes . PhD thesis, UC Santa Barbara, 2023

2023
[16]

Gartland and D

P. Gartland and D. Lokshtanov. Independent set onPk-free graphs in quasi-polynomial time. In S. Irani, editor,61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 613–624. IEEE, 2020

2020
[17]

Gartland, D

P. Gartland, D. Lokshtanov, T. Masarík, M. Pilipczuk, M. Pilipczuk, and P. Rzazewski. Maximum weight independent setingraphswithnolongclawsinquasi-polynomialtime.InB.Mohar, I.Shinkar, andR.O’Donnell, editors, Proceedings of the 56th Annual ACM Symposium on Theory of Computing,...

2024
[18]

Georgakopoulos and P

A. Georgakopoulos and P. Papasoglu. Graph minors and metric spaces. Preprint available athttps://arxiv.org/abs/ 2305.07456, 2023. TREE INDEPENDENCE NUMBER V. W ALLS AND CLA WS 27

2023 arXiv
[19]

D. J. Harvey and D. R. Wood. Parameters tied to treewidth.J. Graph Theory, 84(4):364–385, 2017

2017
[20]

D. König. Gráfok és mátrixok.Matematikai és Fizikai Lapok , 38:116–119, 1931

1931
[21]

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

2024
[22]

F. P. Ramsey. On a Problem of Formal Logic.Proc. London Math. Soc. (2) , 30(4):264–286, 1929

1929
[23]

Robertson and P

N. Robertson and P. D. Seymour. Graph minors. XVI. Excluding a non-planar graph.J. Combin. Theory Ser. B , 89(1):43–76, 2003

2003
[24]

N. Yolov. Minor-matching hypertree width. In A. Czumaj, editor,Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018 , pages 219–233. SIAM, 2018

2018

Pith tools

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

[1] [5]

Induced subgraphs and tree decompositions XV. Even-hole-free graphs with bounded clique number have logarithmic treewidth

M. Chudnovsky, P. Gartland, S. Hajebi, D. Lokshtanov, and S. Spirkl. Induced subgraphs and tree decompositions XV. Even-hole-free graphs have logarithmic treewidth. Preprint available athttps://arxiv.org/abs/2402.14211, 2024

work page Pith review arXiv 2024

[2] [6]

Chudnovsky, S

M. Chudnovsky, S. Hajebi, D. Lokshtanov, and S. Spirkl. Tree independence number II. Three-path-configurations. Preprint available athttps://arxiv.org/abs/2405.00265, 2024

arXiv 2024

[3] [1]

Induced subgraphs and tree decompositions X. Towards logarithmic treewidth for even-hole-free graphs

T. Abrishami, B. Alecu, M. Chudnovsky, S. Hajebi, and S. Spirkl. Induced subgraphs and tree decompositions X. Towards logarithmic treewidth for even-hole-free graphs. Preprint available athttps://arxiv.org/abs/2307.13684, 2024

work page Pith review arXiv 2024

[4] [2]

J. Ahn, J. P. Gollin, T. Huynh, and O. Kwon. A coarse Erdős-Pósa theorem. Preprint available athttps://arxiv.org/ abs/2407.05883, 2024. Accepted for publication in the proceedings of SODA ’25

arXiv 2024

[5] [3]

H. L. Bodlaender. Dynamic programming on graphs with bounded treewidth. InAutomata, languages and programming (Tampere, 1988), volume 317 ofLecture Notes in Comput. Sci. , pages 105–118. Springer, Berlin, 1988

work page 1988

[6] [4]

Graphs with no long claws: An improved bound for the analog of the Gy\'{a}rf\'{a}s' path argument

R. Bourneuf, J. Masaříková, W. Nadara, and M. Pilipczuk. Graphs with no long claws: An improved bound for the analog of the Gyárfás path argument. Preprint available athttps://arxiv.org/abs/2501.13907, 2025

work page Pith review arXiv 2025

[7] [7]

Chudnovsky, M

M. Chudnovsky, M. Pilipczuk, M. Pilipczuk, and S. Thomassé. Quasi-polynomial time approximation schemes for the maximum weight independent set problem inH-free graphs. SIAM Journal on Computing , 53(1):47–86, 2024

work page 2024

[8] [8]

Chudnovsky and P

M. Chudnovsky and P. Seymour. The three-in-a-tree problem.Combinatorica, 30:387–417, 2010

work page 2010