Skip to content
DraconiticResearch
Search Sources API
197,768 studies31 sourcesUpdated 17 min ago
Peer-reviewedCC BY-NC 4.0Journal of Graph Theory

Tree Independence Number III. Thetas, Prisms and Stars

  • Maria Chudnovsky
  • Sepehr Hajebi
  • Nicolas Trotignon
Open at sourcePDFDOICite

Abstract

We prove that for every t ∈ N there exists τ = τ (t) ∈ N such that every (theta, prism, K 1,t )-free graph has tree independence number at most τ (where we allow "prisms" to have one path of length zero).

Related

  1. Tree-independence number VIII. 3PC-free graphs have logarithmic tree-independence number
    Maria Chudnovsky, Julien Codsi, Ajaykrishnan E S +2
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  2. Clique-dependent strongly sublinear treewidth and strongly sublinear tree-independence number
    Andrea Munaro
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. Tree-independence number of P5-free graphs with no large bicliques
    Václav Blažej, J. Pascal Gollin, Tomáš Hons +5
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. Sim-Width, Induced Matching Treewidth, and Tree-Independence Number in Induced Kt,t-Free Graphs
    Mengyuan Niu, Xiumei Wang
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. Independence properties for tree beta models
    Yoshihiro Gyotoku, Makiko Sasada, Jacek Wesołowski
    arXivPreprintCC BY 4.0Full textProbabilityarXiv

Cite

BibTeXRIS
BibTeX
@article{chudnovsky2026tree,
  title = {{Tree Independence Number III. Thetas, Prisms and Stars}},
  author = {Maria Chudnovsky and Sepehr Hajebi and Nicolas Trotignon},
  journal = {Journal of Graph Theory},
  year = {2026},
  month = jun,
  doi = {10.1002/jgt.70088},
  url = {https://hal.science/hal-05763869v1},
  note = {CC BY-NC 4.0},
}
RIS
TY  - JOUR
TI  - Tree Independence Number III. Thetas, Prisms and Stars
AU  - Maria Chudnovsky
AU  - Sepehr Hajebi
AU  - Nicolas Trotignon
PY  - 2026
DA  - 2026/06/17
JO  - Journal of Graph Theory
DO  - 10.1002/jgt.70088
UR  - https://hal.science/hal-05763869v1
AB  - We prove that for every t ∈ N there exists τ = τ (t) ∈ N such that every (theta, prism, K 1,t )-free graph has tree independence number at most τ (where we allow "prisms" to have one path of length zero).
SN  - 0364-9024
SN  - 1097-0118
ER  -