A simple layered-wheel-like construction

Bartosz Walczak; David Fischer; Maria Chudnovsky; Sepehr Hajebi; Sophie Spirkl

REVIEW 4 major objections 3 minor 23 references

A simple layered-wheel-like construction

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

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

Pith's one-line read The paper builds simple layered-wheel-like graphs of unbounded treewidth that simultaneously have arbitrarily large girth and no large outerstring induced subgraph of large treewidth, giving the first high-girth counterexample to…

desk verdict Simple new layered-wheel construction with high-girth counterexample to Trotignon's conjecture; the seven-path bound survives scrutiny, though Lemma 2.2 should be expanded. read the letter →

arxiv 2507.06169 v3 pith:6R3GUMVD submitted 2025-07-08 math.CO cs.DM

Maria Chudnovsky , David Fischer , Sepehr Hajebi , Sophie Spirkl , Bartosz Walczak This is my paper · ORCID

classification math.COcs.DM MSC 05C8305C7505C62

keywords layeredwheelstreewidthinducedminorsouterstringgraphsgirththetacompletebipartiteseries-parallel

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 produces a family of graphs, one for each pair of parameters $(g,k)$, whose treewidth grows with $k$ while their girth grows with $g$. The graphs are built from $k$ long paths stacked in layers, with sparse cross-edges placed at carefully chosen indices, so each graph contains a large complete minor whose branching sets are paths. The main theorem shows these graphs contain no large wall and no large complete bipartite graph as an induced minor, keep all vertices of degree at least four far apart, and have the property that every induced subgraph that is an outerstring graph has treewidth bounded by an absolute constant. Because $g$ can be chosen freely, the construction is the first counterexample to Trotignon's conjecture that can also be made to have arbitrarily large girth. The upshot is that the layered-wheel-like obstruction to bounded treewidth persists even in very sparse, high-girth graphs.

What carries the argument

The central object is the layered-wheel-like graph $G^k_g$, built from $k$ paths $P_1,\ldots,P_k$ of length $2k+g$, with cross edges only between equal-index vertices $P_i^x$ and $P_j^x$ when $x=b\cdot 2^{k-j+g}$ for an odd integer $b$; the paths are the branching sets of a linear complete minor model of $K_k$. The proof runs on three mechanisms. First, an induced-subgraph contraction step: after contracting, for each big vertex, the medium vertices attached to it, every induced subgraph becomes a subgraph of a series-parallel graph (a graph of treewidth at most two built by series and parallel compositions), which rules out large wall induced minors. Second, a path-counting step: between any two big vertices there are at most four nonstandard paths, at most two overpasses, and at most one standard non-overpass, yielding at most seven internally anticomplete paths and, through a wide-$\theta$ lemma, ruling out large complete bipartite induced minors. Third, a separator-lifting step: for an outerstring induced subgraph $H$, a contracted minor $H''$ is bipartite with maximum degree at most $8$ unless $H$ already contains a long $\theta$, and $H''$ inherits the absence of large walls; a bounded-degree grid theorem bounds $\operatorname{tw}(H'')$, and balanced separators are lifted back to bound $\operatorname{tw}(H)$.

What would settle it

Look for a concrete failure in the construction: for some $g$ and $k$, find two vertices of degree at least four in $G^k_g$ joined by eight pairwise internally anticomplete paths, which would contradict Corollary 4.5 and break the proof of Lemma 4.1; alternatively, exhibit an induced subgraph of $G^k_g$ that is outerstring and has treewidth greater than the paper's $L$.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1.3: there exist absolute constants $L$ and $t_0$ such that for all $g,k$ there is a graph $G^k_g$ with a linear model of $K_k$ (so treewidth at least $k-1$), no $W_{t_0\times t_0}$ or $K_{t_0,t_0}$ as an induced minor, vertices of degree at least four pairwise at distance at least $2g$, girth at least $g$, and every induced subgraph that is an outerstring graph has treewidth at most $L$. The construction is explicit: take $k$ paths $P_1,\ldots,P_k$ of length $2k+g$, and join vertices $P_i^x$ and $P_j^x$ exactly when $x=b\cdot 2^{k-j+g}$ for odd $b$. The proof is carried by three structural facts: after contracting all medium vertices around big vertices every induced subgraph becomes series-parallel, any two big vertices are joined by at most seven internally anticomplete paths, and any induced subgraph of treewidth larger than $L$ contains a long $\theta$ of length at least $2g-1$. Since long thetas are not outerstring graphs, this gives the outerstring treewidth bound. Thus the graph family is a layered-wheel-like obstruction with arbitrarily large girth, and it refutes Trotignon's conjecture in the stronger high-girth sense.

Load-bearing premise

The proof that no large complete bipartite induced minor appears rests on the case analysis in Section 4, and specifically on the claim that any two big vertices are joined by at most seven pairwise internally anticomplete paths; if some overlooked routing of overpass or non-overpass paths produced an eighth such path, the $K_{t_0,t_0}$-exclusion would fail.

Editorial extensions

If this is right

For every prescribed girth $g$, the construction supplies a graph of treewidth at least $k-1$ that still excludes a fixed wall and a fixed complete bipartite graph as induced minors, so the layered-wheel-like obstruction is compatible with arbitrarily high girth.
Every induced subgraph of $G^k_g$ with treewidth larger than $L$ contains a theta of length at least $2g-1$; hence within this family, large treewidth is witnessed by a long theta, and long thetas are never outerstring graphs.
No earlier layered-wheel construction had all three features at once; this one simultaneously separates high-degree vertices, forbids short cycles, and keeps every outerstring piece small.
The absolute constants $t_0$ and $L$ do not depend on $g$ or $k$, so the counterexample to Trotignon's conjecture is uniform: one fixed exclusion size and one fixed outerstring treewidth bound work at every scale.

Reading between the lines

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

The seven-path bound is probably not tight: the paper notes the argument can be refined to a tight bound of three paths, so a closer case analysis of $G^k_g$ for small $g,k$ should pin down the true maximum number of internally anticomplete paths between two big vertices.
Because the construction is so sparse, it suggests any complete induced-subgraph analog of the grid theorem must be able to express obstructions that are locally tree-like and globally wheel-like; this is an implicit consequence, not stated by the paper.
The separator-lifting argument used here may extend to earlier layered-wheel constructions: if those graphs also have an induced minor of bounded degree and bounded treewidth, the same balancing argument would establish the outerstring property for them as well; this is a testable extension the paper does not pursue.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

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

We should know: this is a simple layered-wheel construction that gives the first high-girth counterexample to Trotignon's conjecture, and the proof is in better shape than the stress-test suggests. The family G^k_g is genuinely new in combining arbitrarily large girth, far-apart degree-four vertices, and bounded treewidth for outerstring induced subgraphs. Previous constructions [5],[12],[22] each miss at least one of these. The series-parallel reduction in Section 3 is clean; the balanced-separator argument in Section 5 is careful and the dependence on Korhonen's theorem is legitimate.

The soft spots are mostly presentational. Lemma 2.2 lists six basic properties—including girth and the distance between big vertices—and dismisses them as 'easy' without proof. For a paper whose selling point is simplicity, that's a small gap in exposition rather than correctness; a referee should ask for a few lines of proof. The constants L, t0, r0 come from cited existential theorems, so no explicit bounds; acceptable for this kind of result.

I checked the stress-test concern about Corollary 4.5. It does not hold up. In Lemma 4.4, the vertex v at index x_alpha lies on the subpath of R*_beta before b_beta, and b_beta is chosen as the first big vertex with layer below l1. Therefore every vertex before b_beta, including v, has layer at least l1, which is strictly larger than l_alpha. That gives the needed adjacency with b_alpha. The construction's switch edges have the big endpoint on the lower layer (the edge rule uses b·2^{k-i+g} with i the lower layer), so the switch endpoint is indeed big. The seven-path bound seems supported.

Who this is for: structural graph theorists working on induced obstructions to treewidth, specifically the layered-wheel program. It is a solid step, not a breakthrough, but it simplifies a crowded topic and refutes a plausible conjecture in a strong form. It deserves a serious referee. My recommendation: send to peer review, with a request to expand the proof of Lemma 2.2 and to double-check the details in Section 4 for the final version.

Referee Report

4 major / 3 minor

Summary. The paper introduces a family of graphs G^k_g, built from k paths with cross-edges placed at dyadic indices, and proves Theorem 1.3: for absolute constants L and t0, every G^k_g contains a linear K_k minor model, is W_{t0×t0}- and K_{t0,t0}-induced-minor-free, has girth at least g, has any two vertices of degree at least four at distance at least 2g, and has every outerstring induced subgraph of treewidth at most L. The proof proceeds in three main blocks: a series-parallel contraction argument to rule out large wall induced minors (Section 3), a counting argument showing at most seven pairwise internally anticomplete paths between any two vertices to rule out wide thetas and hence large complete bipartite induced minors (Section 4), and a balanced-separator argument using Korhonen's bounded-degree theorem to bound the treewidth of outerstring induced subgraphs (Section 5).

Significance. If the construction and proofs are correct, this is a valuable contribution: it provides a substantially simpler layered-wheel-like construction than previous ones, and it is the first such construction that simultaneously has arbitrarily large girth and the outerstring-treewidth property, giving a strong counterexample to Trotignon's conjecture. The high-level architecture is clean, the use of external theorems (Grid Theorem, Korhonen's theorem, balanced-separator lemmas, non-outerstring long thetas) is appropriate, and the claimed features (a), (b), and (c) are genuinely notable. The main weaknesses are that several load-bearing combinatorial checks are either omitted or too compressed to be fully verifiable as written.

major comments (4)

[Section 2, Lemma 2.2] Lemma 2.2 lists six properties that are load-bearing for Theorem 1.3 and for later lemmas, including the girth lower bound (iii) and the distance bound (v), yet the proof is dismissed with 'the proofs are easy and we leave the details to the reader.' These are not immediate from the construction: for instance, (v) must rule out short paths that use combinations of path segments and switching edges between layers, and (iii) must rule out cycles that use several layers. Please provide complete proofs, or a detailed appendix, for all six items.
[Section 4, Lemma 4.4] The proof of Lemma 4.4 does not justify the key claim that if x_alpha < x_1 and x_beta < x_1, then the subpath of R*_beta from R^-_beta to b_beta contains a vertex v with index x_alpha and layer strictly larger than l_alpha. This is true, but only because b_beta is chosen to have minimal distance to R^-_beta among big vertices with layer below l1; any vertex before b_beta on a layer below l1 would force an earlier big vertex below l1. This argument should be written out. Without it, the conclusion that two overpasses cannot have their chosen big vertices on the same side of x1 is unsupported.
[Section 4, Lemma 4.3] In the proof of Lemma 4.3, the statement 'R* switches layers to l at x' ... It follows that R* includes a big vertex with layer at most l and index x'' needs a justification that the lower endpoint of the switching edge is the big vertex. This follows from Construction 2.1 because cross-layer edges only occur when the lower-layer endpoint has the required dyadic index and is therefore big, but the text should say this explicitly.
[Section 5, Lemma 5.9] Lemma 5.9 concludes that if H is outerstring then H'' has maximum degree less than 9 because the theta just constructed contradicts Lemma 5.6. However, Lemma 5.6 only rules out thetas of length at least 4, while the theta obtained has length at least 2g-1; for g=1,2 this lower bound is 1 or 3, and thetas of length 3 (subdivisions of K_{2,3}) are outerstring. Thus the proof of Lemma 5.1 does not cover g=1,2 as written. This can be repaired by proving Lemma 5.1 for g at least 3 and for smaller g using G^{max(g,3)}_k, since the latter has girth at least g and high-degree vertices at distance at least 2g.

minor comments (3)

[Throughout, Construction 2.1 and Figure 2] The text repeatedly displays the path length and index bounds as '2k+g' (for example, Construction 2.1 and Figure 2's P_5^64); this should be 2^{k+g}. As typeset, the construction is internally inconsistent.
[Section 5, Lemma 5.9] The sentence 'a in V(D) subseteq G \ N[b]' should be justified: D is a component of H'\K', and b is in K', but components of H'\K' may still have edges to K'; one must use the fact that neighbors of b in H are medium vertices contained in K' or small path-neighbors of degree at most two.
[Section 6, Theorem 6.2] Theorem 6.2 is stated as a strengthening, but its proof is only sketched; consider adding a sentence explaining that it follows from the same separator argument without the outerstring assumption.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the construction is self-contained and each load-bearing step is verified from explicit definitions or imported from independent published theorems.

full rationale

The paper is a construction-and-verification argument, not a derivation that presupposes its conclusion. The graph G^k_g is defined explicitly in Construction 2.1, and the four properties of Theorem 1.3 are proved separately: Lemma 2.2 gives the linear K_k model, large girth, and distance/degree properties; Lemma 3.1 excludes large walls as induced minors via the series-parallel contraction argument of Lemmas 3.2–3.3; Lemma 4.1 excludes large complete bipartite induced minors using the seven-path bound of Corollary 4.5 together with Lemma 4.2; Lemma 5.1 bounds the treewidth of outerstring induced subgraphs using balanced separators, Korhonen's theorem, and Lemma 5.6. The only author-overlapping citations are [10] (used for Lemma 4.2 and as background Theorem 1.2) and [15] (used for Lemma 5.6), but these are published, parameter-free theorems whose assumptions do not include the present construction and whose conclusions are not equivalent to the target result; they serve as independent external ingredients rather than as premises that smuggle in the conclusion. No equation or definition reduces a claimed prediction to an input by construction, and no fitted parameter is renamed as a prediction. The skeptical concern about the compressed case analysis in Lemmas 4.3–4.4 is a potential correctness or proof-completeness issue, not a circularity issue, because the claimed bound of seven paths is derived from the explicit definition of the graph and does not assume the nonexistence of K_{r0,r0}. Therefore the paper exhibits no significant circularity.

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

No fitted or hand-chosen numeric parameters appear; g and k are construction variables, and L, t0, h0, r0, L'' are existential constants from cited theorems. The graph family G^k_g is explicitly constructed and testable, so it is not a postulated entity. All axioms are published mathematical theorems or standard background.

assumptions (7)

standard math Grid Theorem (Theorem 1.1, Robertson and Seymour [21]): every graph of treewidth at least f(k) contains a subdivision of W_{k x k} as a subgraph.
Assumed as background in Section 1.1 to motivate the induced-obstruction program; not used to prove the main construction.
standard math Corollary of Lemma 3.6 in [1] (Aboulker et al.): every graph containing W_{h x h} as an induced minor contains a subdivision of W_{t x t} or the line graph of a subdivision of W_{t x t} as an induced subgraph.
Used in the proof of Lemma 3.1 to reduce walls to subdivisions; since G^k_g is triangle-free, the line-graph case is excluded.
standard math Lemma 4.2 (Chudnovsky, Hajebi, Spirkl [10]): if G contains no wide theta of width 8 and no W_{h x h} induced minor, then G contains no K_{r,r} induced minor.
Pulls the K_{r0,r0}-free result from the bound on internally anticomplete paths and the wall-free result in Section 4.
standard math Balanced separator lemmas (Lemmas 5.2 and 5.3, from [2,4,17,20] and [4,13,20]): weight-balanced separators of size m imply treewidth at most 2m, and any weak weight function has a balanced separator of size tw+1.
Bridges from separator size to treewidth in Section 5.
standard math Theorem 5.4 (Korhonen [18]): for fixed d and t, the class of bounded-degree graphs avoiding subdivisions of walls and their line graphs as induced subgraphs has bounded treewidth.
Used in Corollary 5.10 to bound the treewidth of H'' once its maximum degree is less than 9.
standard math Lemma 5.6 (implicit in Davies, Krawczyk, McCarty, Walczak [15]): ell-long thetas for ell >= 4 are not outerstring graphs.
Key external fact used to force maximum degree below 9 in H'' for outerstring graphs; the paper provides a short proof using Proposition 6.2 of [15].
standard math Lemma 5.8 (from Abrishami et al. [2,3]): structural classification of a minimal connected induced subgraph containing neighbors of three vertices in a triangle-free graph.
Used in Lemma 5.9 to find a theta when H'' has a high-degree component.

how reviews work

0 comments

Cite this review

Pith. "Pith review of A simple layered-wheel-like construction." pith.science (2026). https://pith.science/paper/6R3GUMVD

@misc{pith2026250706169,
  author       = {Pith},
  title        = {Pith review of: A simple layered-wheel-like construction},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/6R3GUMVD}},
  note         = {Machine review of arXiv:2507.06169}
}

read the original abstract

In recent years, there has been significant interest in characterizing the induced subgraph obstructions to bounded treewidth and pathwidth. While this has recently been resolved for pathwidth, the case of treewidth remains open, and prior work has reduced the problem to understanding the layered-wheel-like obstructions -- graphs that contain large complete minor models with each branching set inducing a path; exclude large walls as induced minors; exclude large complete bipartite graphs as induced minors; and exclude large complete subgraphs. There are various constructions of such graphs, but they are all rather involved. In this paper, we present a simple construction of layered-wheel-like graphs with arbitrarily large treewidth. Three notable features of our construction are: (a) the vertices of degree at least four can be made to be arbitrarily far apart; (b) the girth can be made to be arbitrarily large; and (c) every outerstring induced subgraph of the graphs from our construction has treewidth bounded by an absolute constant. In contrast, among several previously known constructions of layered wheels, none achieves (a); at most one satisfies either (b) or (c); and none satisfies both (b) and (c) simultaneously. In particular, this is related to a former conjecture of Trotignon, that every graph with large enough treewidth, excluding large walls and large complete bipartite graphs as induced minors, and large complete subgraphs, must contain an outerstring induced subgraph of large treewidth. Our construction provides the first counterexample to this conjecture that can also be made to have arbitrarily large girth.

Figures

Figures reproduced from arXiv: 2507.06169 by the authors.

**Figure 1.** W5×5 (and deleting the loops and the parallel edges produced in the contraction process). A tree decomposition (T, χ) of G consists of a tree T and a map χ: V (T) → 2 V (G) such that the following hold. • For every vertex v ∈ V (G), there exists t ∈ V (T) such that v ∈ χ(t). • For every edge v1v2 ∈ E(G), there exists t ∈ V (T) such that v1, v2 ∈ χ(t). • For every v ∈ V (G), the subgraph of T induced by {t ∈ V (T): v… view at source ↗

**Figure 2.** G1 5 (internal small vertices are not drawn) 2. The main construction In this section, we give the description of the graph family that proves Theorem 1.3. Construction 2.1. For g, k ∈ N, let G g k be the graph constructed as follows. (i) V (G g k ) is partitioned into k paths P1, . . . , Pk of length 2 k+g , where Pi = P 0 i -· · ·-P 2 k+g i for each i with 1 ≤ i ≤ k. (ii) For all i and j with 1 ≤ i < j ≤ k, the ve… view at source ↗

**Figure 3.** A nonstandard path between two (enlarged) big vertices In particular, if u and v are not both in B(G g k ), there can be no more than three pairwise internally anticomplete paths between the two. Thus, we need only consider paths between two big vertices in G g k . We recall the notation used in defining G g k . Suppose b1 = P x1 ℓ1 ∈ B(G g k ) and b2 = P x2 ℓ2 ∈ B(G g k ) are two distinct vertices of G g k ; by the… view at source ↗

Figures from the paper (2 more)

**Figure 4.** Figure 4: An overpass between two (enlarged) big vertices Now assume that there is at least one element of R′ that is not an overpass; let b = P x0 ℓ0 be a big vertex contained in some non-overpass of R′ such that x1 < x0 < x2 and ℓ0 is minimal. Let R∗ 0 be the element of R′ con…

**Figure 5.** Figure 5: An illustration of the theta that appears in H when H′′ has maximum degree at least 9. Let X ⊆ D be minimal (with respect to inclusion) such that H[X] is connected and contains at least one neighbor of each of n1, n2, n3. We now apply Lemma 5.8 with n1, n2, n3 and H[X]…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

23 extracted references · 22 canonical work pages

[5]

Every graph is essential to large treewidth

B. Alecu, É. Bonnet, P. Bureo Villafana, and N. Trotignon. “Every graph is essential to large treewidth.” arXiv:2502.14775, 2025

arXiv 2025
[12]

On treewidth and maximum cliques

M. Chudnovsky and N. Trotignon. “On treewidth and maximum cliques.”Innovations in Graph Theory 2, 223–243, 2025

work page 2025
[22]

(Theta, triangle)-free and (even hole,K4)-free graphs. Part 1: Layered wheels

N. Sintiari and N. Trotignon. “(Theta, triangle)-free and (even hole,K4)-free graphs. Part 1: Layered wheels.”Journal of Graph Theory97, 475–509, 2021

work page 2021
[1]

On the tree-width of even-hole-free graphs

P. Aboulker, I. Adler, E. Kim, N. Sintiari, and N. Trotignon. “On the tree-width of even-hole-free graphs.” European Journal of Combinatorics98, 103394, 2021

work page 2021
[2]

Induced subgraphs and tree decompositions II. Toward walls and their line graphs in graphs of bounded degree

T. Abrishami, M. Chudnovsky, C. Dibek, S. Hajebi, P. Rzążewski, S. Spirkl, and K. Vušković. “Induced subgraphs and tree decompositions II. Toward walls and their line graphs in graphs of bounded degree.” Journal of Combinatorial Theory, Series B164, 371–403, 2024

work page 2024
[3]

Submodular functions and perfect graphs

T. Abrishami, M. Chudnovsky, C. Dibek, and K. Vušković. “Submodular functions and perfect graphs.” Mathematics of Operations Research50(1), 189-208, 2025

work page 2025
[4]

Induced subgraphs and tree decompositions V. One neighbor in a hole

T. Abrishami, B. Alecu, M. Chudnovsky, S. Hajebi, S. Spirkl, and K. Vušković. “Induced subgraphs and tree decompositions V. One neighbor in a hole.”Journal of Graph Theory105(4), 542–561, 2023

work page 2023
[6]

Induced subgraphs and tree decompositions XIII. Basic obstructions inH-free graphs for finiteH

B. Alecu, M. Chudnovsky, S. Hajebi, and S. Spirkl. “Induced subgraphs and tree decompositions XIII. Basic obstructions inH-free graphs for finiteH.”Advances in Combinatorics2024, Paper No. 6, 2024

work page 2024

Show all 23 references

[7]

Induced subgraphs and tree decompositions IX. Grid theorem for perforated graphs

B. Alecu, M. Chudnovsky, S. Hajebi, and S. Spirkl. “Induced subgraphs and tree decompositions IX. Grid theorem for perforated graphs.”Advances in Combinatorics2025, Paper No. 3, 2025

2025
[8]

Induced subgraphs and tree decompositions XII. Grid theorem for pinched graphs

B. Alecu, M. Chudnovsky, S. Hajebi, and S. Spirkl. “Induced subgraphs and tree decompositions XII. Grid theorem for pinched graphs.”Innovations in Graph Theory2, 1–23, 2025

2025
[9]

Sparse graphs with bounded induced cycle packing number have logarithmic treewidth

M. Bonamy, É. Bonnet, H. Déprés, L. Esperet, C. Geniet, C. Hilaire, S. Thomassé, and A. Wesolek. “Sparse graphs with bounded induced cycle packing number have logarithmic treewidth.”Journal of Combinatorial Theory, Series B167, 215–249, 2024

2024
[10]

Induced subgraphs and tree decompositions XVI. Complete bipartite induced minors

M. Chudnovsky, S. Hajebi, and S. Spirkl. “Induced subgraphs and tree decompositions XVI. Complete bipartite induced minors.”Journal of Combinatorial Theory, Series B176, 287–318, 2025

2025
[11]

Induced subgraphs and tree decompositions XVII. Anticomplete sets of large treewidth

M. Chudnovsky, S. Hajebi, and S. Spirkl. “Induced subgraphs and tree decompositions XVII. Anticomplete sets of large treewidth.”arXiv:2411.11842, 2024

2024
[13]

Cygan, F

M. Cygan, F. Fomin, Ł. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh. Parameterized Algorithms. Springer, 2015

2015
[14]

Problem Session

J. Davies. In: “Problem Session.”Oberwolfach Reports19(1), 66–67, 2022

2022
[15]

Coloring polygon visibility graphs and their generalizations

J. Davies, T. Krawczyk, R. McCarty, and B. Walczak. “Coloring polygon visibility graphs and their generalizations.”Journal of Combinatorial Theory, Series B161, 268–300, 2023

2023
[16]

Parallel recognition of series-parallel graphs

D. Eppstein. “Parallel recognition of series-parallel graphs.”Information and Computation98(1), 41–55, 1992

1992
[17]

Parameters tied to treewidth

D. J. Harvey and D. R. Wood. “Parameters tied to treewidth.”Journal of Graph Theory84(4), 364–385, 2017

2017
[18]

Grid induced minor theorem for graphs of small degree

T. Korhonen. “Grid induced minor theorem for graphs of small degree.”Journal of Combinatorial Theory, Series B160, 206–214, 2023

2023
[19]

Unavoidable induced subgraphs of large graphs

A. C. Pohoata. “Unavoidable induced subgraphs of large graphs.” Senior thesis, Princeton University, 2014

2014
[20]

Graph minors. II. Algorithmic aspects of tree-width

N. Robertson and P. Seymour. “Graph minors. II. Algorithmic aspects of tree-width.”Journal of Algorithms7(3), 309–322, 1986

1986
[21]

Graph minors. V. Excluding a planar graph

N. Robertson and P. Seymour. “Graph minors. V. Excluding a planar graph.”Journal of Combinatorial Theory, Series B41(1), 92–114, 1996

1996
[23]

Trotignon

N. Trotignon. Private communication, 2025

2025

Pith tools

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

[1] [5]

Every graph is essential to large treewidth

B. Alecu, É. Bonnet, P. Bureo Villafana, and N. Trotignon. “Every graph is essential to large treewidth.” arXiv:2502.14775, 2025

arXiv 2025

[2] [12]

On treewidth and maximum cliques

M. Chudnovsky and N. Trotignon. “On treewidth and maximum cliques.”Innovations in Graph Theory 2, 223–243, 2025

work page 2025

[3] [22]

(Theta, triangle)-free and (even hole,K4)-free graphs. Part 1: Layered wheels

N. Sintiari and N. Trotignon. “(Theta, triangle)-free and (even hole,K4)-free graphs. Part 1: Layered wheels.”Journal of Graph Theory97, 475–509, 2021

work page 2021

[4] [1]

On the tree-width of even-hole-free graphs

P. Aboulker, I. Adler, E. Kim, N. Sintiari, and N. Trotignon. “On the tree-width of even-hole-free graphs.” European Journal of Combinatorics98, 103394, 2021

work page 2021

[5] [2]

Induced subgraphs and tree decompositions II. Toward walls and their line graphs in graphs of bounded degree

T. Abrishami, M. Chudnovsky, C. Dibek, S. Hajebi, P. Rzążewski, S. Spirkl, and K. Vušković. “Induced subgraphs and tree decompositions II. Toward walls and their line graphs in graphs of bounded degree.” Journal of Combinatorial Theory, Series B164, 371–403, 2024

work page 2024

[6] [3]

Submodular functions and perfect graphs

T. Abrishami, M. Chudnovsky, C. Dibek, and K. Vušković. “Submodular functions and perfect graphs.” Mathematics of Operations Research50(1), 189-208, 2025

work page 2025

[7] [4]

Induced subgraphs and tree decompositions V. One neighbor in a hole

T. Abrishami, B. Alecu, M. Chudnovsky, S. Hajebi, S. Spirkl, and K. Vušković. “Induced subgraphs and tree decompositions V. One neighbor in a hole.”Journal of Graph Theory105(4), 542–561, 2023

work page 2023

[8] [6]

Induced subgraphs and tree decompositions XIII. Basic obstructions inH-free graphs for finiteH

B. Alecu, M. Chudnovsky, S. Hajebi, and S. Spirkl. “Induced subgraphs and tree decompositions XIII. Basic obstructions inH-free graphs for finiteH.”Advances in Combinatorics2024, Paper No. 6, 2024

work page 2024