pith. sign in

arxiv: 2605.01223 · v1 · submitted 2026-05-02 · 🧮 math.CO

Tree-alpha and excluding finitely many graphs

Sepehr Hajebi , Sophie Spirkl This is my paper

Pith reviewed 2026-05-09 15:09 UTC · model grok-4.3

classification 🧮 math.CO
keywords hereditary graph classesforbidden induced subgraphstree-alphatreewidthboundednesscomplete bipartite graphsforests
0
0 comments X

The pith

Hereditary graph classes defined by finitely many forbidden induced subgraphs have bounded tree-α exactly when they exclude a complete bipartite graph, certain forests, and their line graphs.

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

The paper proves an if-and-only-if characterization for when such classes have bounded tree-α. It equates this property with the class being (tw,ω)-bounded, meaning that for every fixed t the K_t-free graphs inside the class have bounded treewidth. The characterization is given explicitly by the forbidden induced subgraphs: any complete bipartite graph, any forest whose components have at most three leaves, and the line graph of any such forest. This settles two open conjectures, including the statement that every hereditary class excluding both K_{a,a} and a path on b vertices has bounded tree-α for all a and b.

Core claim

A hereditary graph class G defined by finitely many excluded induced subgraphs has bounded tree-α if and only if it is (tw,ω)-bounded. Equivalently, G has bounded tree-α if and only if it excludes a complete bipartite graph, a forest whose components each have at most three leaves, and the line graph of such a forest.

What carries the argument

The equivalence between bounded tree-α and (tw,ω)-boundedness, which supplies an explicit list of three types of forbidden induced subgraphs that completely determine the property for finitely defined hereditary classes.

Load-bearing premise

The graph class must be hereditary and defined by only finitely many excluded induced subgraphs.

What would settle it

A hereditary class defined by finitely many forbidden induced subgraphs in which tree-α is bounded but some K_t-free subclass has unbounded treewidth, or the converse.

Figures

Figures reproduced from arXiv: 2605.01223 by Sepehr Hajebi, Sophie Spirkl.

Figure 1
Figure 1. Figure 1: Left: A subdivided multiclaw F with four components (top) and its line graph (bottom). Right: The 7-by-7 wall contains an induced copy of F, and so (the line graph of) every subdivision of the same wall contains an induced copy of (the line graph of) F. More generally, the tree independence (or stability) number of a graph G [24, 36], denoted tree-α(G), is the minimum c ∈ N for which G admits a tree decomp… view at source ↗
read the original abstract

We prove that a hereditary graph class $\mathcal{G}$ defined by finitely many excluded induced subgraphs has bounded tree-$\alpha$ if and only if it is "$(\mathrm{tw},\omega)$-bounded" (that is, for all $t\in \mathbb N$, the class of all $K_t$-free graphs in $\mathcal{G}$ has bounded treewidth). Equivalently, $\mathcal{G}$ has bounded tree-$\alpha$ if and only if it excludes a complete bipartite graph, a forest whose components each have at most three leaves, and the line graph of such a forest. This resolves two conjectures of Dallard, Krnc, Kwon, Milani\v{c}, Munaro, \v{S}torgel, and Wiederrecht: the above, and a weaker one that for all $a,b\in \mathbb N$, every hereditary class that excludes $K_{a,a}$ and the $b$-vertex path has bounded tree-$\alpha$. The latter was already open even for $(a,b)\in \{(2,7),(3,5)\}$, and only recently proved for $(a,b)=(2,6)$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The paper proves that a hereditary graph class G defined by finitely many excluded induced subgraphs has bounded tree-α if and only if it is (tw,ω)-bounded. Equivalently, G has bounded tree-α precisely when it excludes a complete bipartite graph, a forest whose components each have at most three leaves, and the line graph of such a forest. This resolves two conjectures of Dallard et al., including a weaker conjecture that was open even for specific pairs such as (a,b) = (2,7) and (3,5).

Significance. If the result holds, it supplies a clean structural characterization of bounded tree-α in the setting of finitely-forbidden hereditary classes, confirming two open conjectures with a complete proof. The argument uses only standard facts about tree decompositions, independence numbers, and induced-subgraph-closed classes, together with an exhaustive case analysis on the listed minimal obstructions. This is a substantive advance for the study of treewidth and α-boundedness in restricted graph families.

minor comments (2)
  1. The abstract states the main equivalences clearly, but the introduction would benefit from a short paragraph outlining the two directions of the proof before the detailed case analysis begins.
  2. Notation for tree-α and (tw,ω)-boundedness is introduced early and used consistently; a single sentence reminding the reader of the precise definition of tree-α (maximum independence number over bags in a tree decomposition) would aid readers who encounter the paper in isolation.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the manuscript and for recommending acceptance. The report correctly captures the main theorem and its resolution of the two conjectures from Dallard et al.

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained

full rationale

The manuscript establishes an if-and-only-if equivalence for hereditary classes with finitely many forbidden induced subgraphs by proving both directions via standard structural arguments on tree decompositions, independence numbers, and minimal obstructions (complete bipartite graphs, 3-leaf forests, and their line graphs). These steps rely on well-established facts about treewidth and induced-subgraph-closed classes rather than any self-definition, fitted parameters renamed as predictions, or load-bearing self-citations. The resolution of the cited conjectures from Dallard et al. is external and does not reduce the central claim to its own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

This is a pure mathematical characterization theorem. It introduces no free parameters, no new postulated entities, and relies only on standard definitions and axioms from graph theory.

axioms (2)
  • standard math Basic definitions and closure properties of hereditary graph classes under induced subgraphs.
    The theorem is stated specifically for hereditary classes defined by finitely many excluded induced subgraphs.
  • standard math Standard definitions of tree-alpha, treewidth, clique number omega, and related width parameters.
    These are invoked directly in the statement of the (tw, omega)-boundedness property.

pith-pipeline@v0.9.0 · 5499 in / 1320 out tokens · 50031 ms · 2026-05-09T15:09:57.131588+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

35 extracted references · 10 canonical work pages · 1 internal anchor

  1. [1]

    Abrishami, B

    T. Abrishami, B. Alecu, M. Chudnovsky, S. Hajebi, and S. Spirkl. Induced subgraphs and tree decompositions VII. Basic obstructions inH-free graphs.J. Combin. Theory Ser. B, 164:443–472, 2024

    2024

  2. [2]

    Abrishami, B

    T. Abrishami, B. Alecu, M. Chudnovsky, S. Hajebi, and S. Spirkl. Induced subgraphs and tree decompositions VIII: Excluding a forest in (theta, prism)-free graphs.Combinatorica, 44(5):921–948, 2024

    2024

  3. [3]

    Abrishami, M

    T. Abrishami, M. Briański, J. Czyżewska, R. McCarty, M. Milanič, P. Rzążewski, and B. Walczak. Excluding a clique or a biclique in graphs of bounded induced matching treewidth.SIAM J. Discrete Math., 39(2):1189–1200, 2025

    2025

  4. [4]

    Alecu, M

    B. Alecu, M. Chudnovsky, S. Hajebi, and S. Spirkl. Induced subgraphs and tree decompositions XI. Local structure in even-hole-free graphs of large treewidth. Manuscript available athttps: //arxiv.org/abs/2309.04390, 2023

    work page arXiv 2023

  5. [5]

    Alecu, M

    B. Alecu, M. Chudnovsky, S. Hajebi, and S. Spirkl. Induced subgraphs and tree decompositions XIII. Basic obstructions inH-free graphs for finiteH.Adv. Comb., pages Paper No. 6, 30, 2024

    2024

  6. [6]

    Alecu, M

    B. Alecu, M. Chudnovsky, S. Hajebi, and S. Spirkl. Induced subgraphs and tree decompositions IX. Grid theorem for perforated graphs.Adv. Comb., pages Paper No. 3, 40, 2025

    2025

  7. [7]

    Alecu, M

    B. Alecu, M. Chudnovsky, S. Hajebi, and S. Spirkl. Induced subgraphs and tree decompositions XII. Grid theorem for pinched graphs.Innov. Graph Theory, 2:1–23, 2025

    2025

  8. [8]

    K. B. Štorgel, M. Milanič, V. Lozin, and V. Zamaraev. Awesome graph parameters. Available at https://arxiv.org/abs/2511.05285, 2025

    work page arXiv 2025

  9. [9]

    Bonamy, E

    M. Bonamy, E. 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.J. Combin. Theory Ser. B, 167:215–249, 2024

    2024

  10. [10]

    M. Choi, C. Hilaire, M. Milanič, and S. Wiederrecht. Excluding an induced wheel minor in graphs without large induced stars. InGraph-theoretic concepts in computer science, volume 16124 of Lecture Notes in Comput. Sci., pages 135–148. 2026

    2026

  11. [11]

    Chudnovsky and J

    M. Chudnovsky and J. Codsi. Tree independence number VI. Thetas and pyramids. Manuscript available athttps://arxiv.org/abs/2509.15458, 2025. 18 TREE-ALPHA AND EXCLUDING FINITELY MANY GRAPHS

    work page arXiv 2025

  12. [12]

    Chudnovsky, J

    M. Chudnovsky, J. Codsi, J. P. Gollin, M. Milanič, and V. Sivashankar. Tree-independence number and forbidden induced subgraphs: excluding a6-vertex path and a(2, t)-biclique. Manuscript available athttps://arxiv.org/abs/2604.01999, 2026

    work page arXiv 2026

  13. [13]

    Induced subgraphs and tree decompositions XIX

    M. Chudnovsky, J. Codsi, S. Hajebi, and S. Spirkl. Induced subgraphs and tree decompositions XIX. thetas and trees. Manuscript available athttps://arxiv.org/abs/2506.05602, 2025

    work page arXiv 2025

  14. [14]

    Chudnovsky, J

    M. Chudnovsky, J. Codsi, D. Lokshtanov, M. Milanič, and V. Sivashankar. Tree independence number v. Walls and claws. Manuscript available athttps://arxiv.org/abs/2501.14658, 2025

    work page arXiv 2025

  15. [16]

    Chudnovsky, S

    M. Chudnovsky, S. Hajebi, D. Lokshtanov, and S. Spirkl. Tree independence number II. Three-path-configurations.J. Combin. Theory Ser. B, 176:74–96, 2026

    2026

  16. [17]

    Chudnovsky, S

    M. Chudnovsky, S. Hajebi, and S. Spirkl. Induced subgraphs and tree decompositions XVII. Anticomplete sets of large of treewidth. Manuscript available athttps://arxiv.org/abs/2411. 11842, 2024

    2024

  17. [18]

    Chudnovsky, S

    M. Chudnovsky, S. Hajebi, and S. Spirkl. Induced subgraphs and tree decompositions XVIII. Obstructions to bounded pathwidth. Manuscript available athttps://arxiv.org/abs/2412. 17756, 2024

    2024

  18. [19]

    M.Chudnovsky,S.Hajebi,andS.Spirkl.InducedsubgraphsandtreedecompositionsXVI.Complete bipartite induced minors.Journal of Combinatorial Theory, Series B, 176:287–318, 2026

    2026

  19. [20]

    (Treewidth, Clique)-Boundedness and Poly-logarithmic Tree-Independence

    M.Chudnovsky,A.E.S,andD.Lokshtanov.(Treewidth,Clique)-BoundednessandPoly-logarithmic Tree-Independence. Manuscript available athttps://arxiv.org/abs/2510.15074, 2025

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  20. [21]

    Chudnovsky and N

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

    2025

  21. [22]

    Cicalese and M

    F. Cicalese and M. Milanič. Graphs of separability at most 2.Discrete Appl. Math., 160(6):685–696, 2012

    2012

  22. [23]

    Treewidth versus clique number

    C. Dallard, M. Krnc, O. Kwon, M. Milanič, A. Munaro, K. Štorgel, , and S. Wiederrecht. Treewidth versuscliquenumber.iv.Tree-independencenumberofgraphsexcludinganinducedstar.Manuscript available athttps://arxiv.org/abs/2402.11222, 2024

    work page arXiv 2024

  23. [24]

    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

  24. [25]

    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

  25. [26]

    Diestel.Graph theory, volume 173 ofGraduate Texts in Mathematics

    R. Diestel.Graph theory, volume 173 ofGraduate Texts in Mathematics. Springer, Berlin, fifth edition, 2018

    2018

  26. [27]

    R. L. Graham and B. L. Rothschild. Ramsey’s theorem forn-parameter sets.Transactions of the American Mathematical Society, 159:257–292, 1971

    1971

  27. [28]

    R. L. Graham, B. L. Rothschild, and J. H. Spencer.Ramsey theory. Wiley Series in Discrete Mathematics and Optimization. John Wiley & Sons, Inc., Hoboken, NJ, paperback edition, 2013

    2013

  28. [29]

    S. Hajebi. Polynomial bounds for pathwidth. Manuscript available athttps://arxiv.org/abs/ 2510.19120, 2025

    work page arXiv 2025

  29. [30]

    Hilaire, M

    C. Hilaire, M. Milanič, and D. Vasić. Treewidth versus clique number. V. Further connections with tree-independence number.Journal of Graph Theory.Available athttps://doi.org/10.1002/jgt. 70036

    work page doi:10.1002/jgt

  30. [31]

    Lozin and I

    V. Lozin and I. Razgon. Tree-width dichotomy.European J. Combin., 103:Paper No. 103517, 8, 2022

    2022

  31. [32]

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

    1929

  32. [33]

    N.RobertsonandP.Seymour.Graphminors.V.Excludingaplanargraph.Journal of Combinatorial Theory, Series B, 41(1):92–114, 1986

    1986

  33. [34]

    Robertson and P

    N. Robertson and P. D. Seymour. Graph minors. I. Excluding a forest.J. Combin. Theory Ser. B, 35(1):39–61, 1983

    1983

  34. [35]

    N. L. D. Sintiari and N. Trotignon. (Theta, triangle)-free and (even hole,K4)-free graphs—part 1: Layered wheels.J. Graph Theory, 97(4):475–509, 2021

    2021

  35. [36]

    N. Yolov. Minor-matching hypertree width. InProceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 219–233. SIAM, Philadelphia, PA, 2018

    2018