pith. sign in

arxiv: 2606.20256 · v1 · pith:IO2OI7U3new · submitted 2026-06-18 · 🧮 math.CO

Tree-independence number of K_(1,d)-free graph classes

Kenny Be\v{s}ter \v{S}torgel , Mujin Choi , Hidde Koerts , {\DH}or{\dj}e Vasi\'c This is my paper

Pith reviewed 2026-06-26 16:57 UTC · model grok-4.3

classification 🧮 math.CO
keywords tree-independence numberK_{1,d}-free graphsouterstring graphsinduced minorgraph classesbounded parametersintersection graphs
0
0 comments X

The pith

K_{1,d}-free outerstring graphs have bounded tree-independence number.

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

The paper shows that for any fixed positive integer d, the tree-independence number remains bounded across all K_{1,d}-free outerstring graphs. This verifies a conjecture of Dallard et al. that K_{1,d}-free graphs avoiding any fixed planar graph as an induced minor have this boundedness property, at least when restricted to outerstring graphs. Bounded tree-independence number yields polynomial-time algorithms for independent set and several other NP-hard problems on the resulting classes. The authors also supply explicit linear and quadratic upper bounds on the parameter for additional K_{1,d}-free families and extend the bound to K_{2,d}-free graphs that contain no holes of length five or longer.

Core claim

For every positive integer d the class of all K_{1,d}-free outerstring graphs has bounded tree-independence number. This confirms the Dallard et al. conjecture for outerstring graphs. Linear and quadratic upper bounds are derived for the tree-independence number in several other K_{1,d}-free classes, and the parameter is shown to be bounded for K_{2,d}-free graphs that additionally forbid holes of length at least five.

What carries the argument

Tree decomposition in which every bag induces a subgraph of bounded independence number, applied via the intersection representation of outerstring graphs under the K_{1,d} forbidden induced subgraph.

If this is right

  • Maximum independent set and several related problems become polynomial-time solvable on K_{1,d}-free outerstring graphs.
  • The Dallard et al. conjecture holds when the host class is outerstring graphs.
  • Improved explicit linear and quadratic bounds replace earlier estimates for multiple K_{1,d}-free families.
  • K_{2,d}-free graphs without long holes also admit bounded tree-independence number.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same boundedness may extend to wider families of string graphs if their geometric representations support analogous bag-control arguments.
  • Bounded tree-independence number could imply polynomial-time coloring or clique-cover algorithms on these classes under additional restrictions.
  • The conjecture remains open for other natural induced-minor-closed families beyond outerstring graphs.

Load-bearing premise

The intersection representation of outerstring graphs permits a decomposition or charging argument that controls independence numbers inside bags once K_{1,d} is forbidden.

What would settle it

An explicit family of K_{1,d}-free outerstring graphs whose tree-independence number grows unboundedly with the number of vertices.

Figures

Figures reproduced from arXiv: 2606.20256 by {\DH}or{\dj}e Vasi\'c, Hidde Koerts, Kenny Be\v{s}ter \v{S}torgel, Mujin Choi.

Figure 1
Figure 1. Figure 1: Containment relations of graph classes in our paper. Graph classes contained in the red part have [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Outerstring graphs in Lemma 14: (Left) We can find an area [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: In the proof of Theorem 17 we can merge two closed curve using a curve between them. [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: G3×4 and its corresponding circle containment representation. Claim 22.1. For any graph H there exists an nH ∈ N + such that RnH,nH contains an induced minor model X of H where for each u ∈ V (H) the branch set Xu ∈ X is given by {vi,j : i ∈ Iu, j ∈ Ju} for some subsets Iu, Ju ⊆ [nH]. We will proceed by induction on |V (H)|. For |V (H)| = 1, the claim trivially holds with nH = 1. Now suppose that |V (H)| ≥… view at source ↗
read the original abstract

In this paper, we investigate the tree-independence number of graph classes that do not contain $K_{1,d}$ as an induced subgraph. Dallard et al. conjectured 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. Our main contribution towards this conjecture is showing that the conjecture holds for outerstring graphs. Additionally we give linear and quadratic bounds for the tree-independence number of various $K_{1,d}$-free graph classes, sharpening previous bounds. Finally, we bound the tree-independence number of $K_{2,d}$-free graphs additionally forbidding holes of length at least $5$.

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 / 1 minor

Summary. The paper proves that for any fixed d, the class of K_{1,d}-free outerstring graphs has bounded tree-independence number, thereby confirming the Dallard et al. conjecture in this case. It additionally derives linear and quadratic upper bounds on the tree-independence number for several other K_{1,d}-free classes (sharpening earlier results) and establishes a bound for K_{2,d}-free graphs that additionally forbid holes of length at least 5.

Significance. If the proofs hold, the work supplies a concrete positive case for the conjecture on K_{1,d}-free H-minor-free graphs when H is planar, using direct combinatorial arguments on the intersection structure of outerstring graphs. The sharpened linear/quadratic bounds are explicit and improve the state of the art for algorithmic applications that rely on tree-independence number.

minor comments (1)
  1. The abstract and introduction would benefit from a brief sentence clarifying whether the outerstring result is obtained via a direct charging argument or via reduction to a known bounded-treewidth case.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the manuscript and their recommendation to accept. No major comments were provided in the report.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper establishes a combinatorial bound on the tree-independence number for the class of K_{1,d}-free outerstring graphs via structural decomposition arguments on intersection graphs, thereby confirming the Dallard et al. conjecture for this family. No load-bearing step reduces by definition, by fitting a parameter to data and renaming the output as a prediction, or by a self-citation chain whose cited result itself depends on the target claim. The derivation is self-contained against external combinatorial benchmarks and does not invoke any of the enumerated circularity patterns.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work rests on standard definitions and lemmas from graph theory and on the statement of the Dallard et al. conjecture; no free parameters or new entities are introduced in the abstract.

axioms (1)
  • standard math Standard axioms and definitions of graph theory (induced subgraphs, minors, intersection graphs).
    Invoked throughout any proof in the area.

pith-pipeline@v0.9.1-grok · 5678 in / 1081 out tokens · 23090 ms · 2026-06-26T16:57:25.286646+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

30 extracted references · 14 canonical work pages

  1. [1]

    Treewidth versus clique number

    Dallard, Cl\'. Treewidth versus clique number. Journal of Combinatorial Theory, Series B , volume =. 2024 , issn =

    2024

  2. [2]

    Treewidth versus clique number

    Dallard, Clément and Krnc, Matjaž and Kwon, O-joung and Milanič, Martin and Munaro, Andrea and Štorgel, Kenny and Wiederrecht, Sebastian , year=. Treewidth versus clique number. 2402.11222 , archivePrefix=

    arXiv

  3. [3]

    Journal of Computer and System Sciences , volume =

    Induced minor models. Journal of Computer and System Sciences , volume =. 2026 , issn =. doi:https://doi.org/10.1016/j.jcss.2025.103738 , author =

    work page doi:10.1016/j.jcss.2025.103738 2026

  4. [4]

    2025 , eprint=

    Excluding a Ladder as an Induced Minor in Graphs Without Induced Stars , author=. 2025 , eprint=

    2025

  5. [5]

    Excluding an Induced Wheel Minor in Graphs Without Large Induced Stars

    Choi, Mujin and Hilaire, Claire and Milani c , Martin and Wiederrecht, Sebastian. Excluding an Induced Wheel Minor in Graphs Without Large Induced Stars. Graph-Theoretic Concepts in Computer Science. 2026. doi:10.1007/978-3-032-11835-6_10

    work page doi:10.1007/978-3-032-11835-6_10 2026

  6. [6]

    1997 , issn =

    Treewidth for graphs with small chordality , journal =. 1997 , issn =. doi:https://doi.org/10.1016/S0166-218X(97)00031-0 , author =

    work page doi:10.1016/s0166-218x(97)00031-0 1997

  7. [7]

    1984 , issn =

    Tolerance graphs , journal =. 1984 , issn =. doi:10.1016/0166-218X(84)90016-7 , author =

    work page doi:10.1016/0166-218x(84)90016-7 1984

  8. [8]

    2016 , issn =

    Tree-chromatic number , journal =. 2016 , issn =. doi:https://doi.org/10.1016/j.jctb.2015.08.002 , author =

    work page doi:10.1016/j.jctb.2015.08.002 2016

  9. [9]

    2025 , issn =

    Comparing width parameters on graph classes , journal =. 2025 , issn =. doi:https://doi.org/10.1016/j.ejc.2025.104163 , author =

    work page doi:10.1016/j.ejc.2025.104163 2025

  10. [10]

    42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025) , pages =

    Ahn, Jungho and Jacob, Hugo and K\". 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025) , pages =. 2025 , volume =

    2025

  11. [11]

    SIAM Journal on Discrete Mathematics , volume =

    Ahn, Jungho and Chakraborti, Debsoumya and Hendrey, Kevin and Oum, Sang-il , title =. SIAM Journal on Discrete Mathematics , volume =. 2025 , doi =

    2025

  12. [12]

    Proceedings of the

    Yolov, Nikola , TITLE =. Proceedings of the. 2018 , ISBN =

    2018

  13. [13]

    Treewidth versus clique number

    Cl. Treewidth versus clique number. Journal of Combinatorial Theory, Series. 2024 , doi =

    2024

  14. [14]

    and Milani

    de Lima, Paloma T. and Milani. Tree Decompositions Meet Induced Matchings: Beyond Max Weight Independent Set , booktitle =. 2024 , doi =

    2024

  15. [15]

    2026 , issn =

    Tree decompositions meet induced matchings: beyond Max Weight Independent Set , journal =. 2026 , issn =. doi:https://doi.org/10.1016/j.jcss.2026.103819 , author =

    work page doi:10.1016/j.jcss.2026.103819 2026

  16. [16]

    Pascal Gollin and Tony Huynh and

    Jungho Ahn and J. Pascal Gollin and Tony Huynh and. Proceedings of the 2025 Annual. 2025 , doi =

    2025

  17. [17]

    Journal of Graph Theory , volume =

    Hilaire, Claire and Milanič, Martin and Vasić, Ðorđe , title =. Journal of Graph Theory , volume =. doi:https://doi.org/10.1002/jgt.70036 , year =

    work page doi:10.1002/jgt.70036

  18. [18]

    Tree-independence number

    Chudnovsky, Maria and Czy. Tree-independence number. 2025 , eprint =

    2025

  19. [19]

    Ramsey, F. P. , title =. Proceedings of the London Mathematical Society , volume =. doi:https://doi.org/10.1112/plms/s2-30.1.264 , eprint =

    work page doi:10.1112/plms/s2-30.1.264

  20. [20]

    Innovations in Graph Theory , pages =

    Chudnovsky, Maria and Trotignon, Nicolas , title =. Innovations in Graph Theory , pages =. 2025 , publisher =. doi:10.5802/igt.11 , language =

    work page doi:10.5802/igt.11 2025

  21. [21]

    Walls and claws , author=

    Tree independence number V. Walls and claws , author=. 2025 , eprint=

    2025

  22. [22]

    2026 , eprint=

    Tree-independence number and forbidden induced subgraphs: excluding a 6 -vertex path and a (2,t) -biclique , author=. 2026 , eprint=

    2026

  23. [23]

    Graph Minors

    Graph minors. Journal of Combinatorial Theory, Series B , volume =. 1986 , issn =. doi:https://doi.org/10.1016/0095-8956(86)90030-4 , author =

    work page doi:10.1016/0095-8956(86)90030-4 1986

  24. [24]

    2023 , issn =

    Grid induced minor theorem for graphs of small degree , journal =. 2023 , issn =. doi:https://doi.org/10.1016/j.jctb.2023.01.002 , author =

    work page doi:10.1016/j.jctb.2023.01.002 2023

  25. [25]

    1967 , doi =

    Transitiv orientierbare Graphen , journal =. 1967 , doi =

    1967

  26. [26]

    European Journal of Combinatorics , volume =

    Coloring. European Journal of Combinatorics , volume =. 2012 , note =. doi:https://doi.org/10.1016/j.ejc.2011.09.021 , author =

    work page doi:10.1016/j.ejc.2011.09.021 2012

  27. [27]

    32nd Annual European Symposium on Algorithms (ESA 2024) , pages =

    An, Shinwoo and Oh, Eunjin and Xue, Jie , title =. 32nd Annual European Symposium on Algorithms (ESA 2024) , pages =. 2024 , volume =. doi:10.4230/LIPIcs.ESA.2024.10 , annote =

    work page doi:10.4230/lipics.esa.2024.10 2024

  28. [28]

    2025 , howpublished =

    Maria Chudnovsky and Sepehr Hajebi and Nicolas Trotignon , title =. 2025 , howpublished =

    2025

  29. [29]

    2026 , eprint=

    Tree-alpha and excluding finitely many graphs , author=. 2026 , eprint=

    2026

  30. [30]

    Pascal Gollin and Tomáš Hons and Tomáš Masařík and Martin Milanič and Paweł Rzążewski and Ondřej Suchý and Alexandra Wesolek , year=

    Václav Blažej and J. Pascal Gollin and Tomáš Hons and Tomáš Masařík and Martin Milanič and Paweł Rzążewski and Ondřej Suchý and Alexandra Wesolek , year=. Tree-independence number of. 2605.03965 , archivePrefix=

    Pith/arXiv arXiv