Skip to content
DraconiticResearch
Search Sources API
201,642 studies31 sourcesUpdated 17 min ago
PreprintCC BY 4.0arXiv

Tree-independence number VIII. 3PC-free graphs have logarithmic tree-independence number

  • Maria Chudnovsky
  • Julien Codsi
  • Ajaykrishnan E S
  • Daniel Lokshtanov
  • Ilya Maier
Open at sourcePDFDOICite

Abstract

A three-path-configuration is a graph consisting of three pairwise internally vertex-disjoint paths, the union of every two of which is an induced cycle of length at least four. A graph is 3PC-free if no induced subgraph of it is a three-path-configuration. We show that 3PC-free graphs have logarithmic tree-independence number, which is asymptotically best possible.

Related

  1. 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
  2. Sim-Width, Induced Matching Treewidth, and Tree-Independence Number in Induced Kt,t-Free Graphs
    Mengyuan Niu, Xiumei Wang
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. Tree Independence Number III. Thetas, Prisms and Stars
    Maria Chudnovsky, Sepehr Hajebi, Nicolas Trotignon
    Journal of Graph TheoryPeer-reviewedCC BY-NC 4.0Full text2 citedCombinatorics & discrete mathematicsHAL
  4. Strong complete immersions in graphs with independence number two
    Zijian Deng, Chuanshu Wu
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  5. Clique-dependent strongly sublinear treewidth and strongly sublinear tree-independence number
    Andrea Munaro
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{chudnovsky2026treeindependence,
  title = {{Tree-independence number VIII. 3PC-free graphs have logarithmic tree-independence number}},
  author = {Maria Chudnovsky and Julien Codsi and Ajaykrishnan E S and Daniel Lokshtanov and Ilya Maier},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.28865},
  eprint = {2610.28865},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.28865},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Tree-independence number VIII. 3PC-free graphs have logarithmic tree-independence number
AU  - Maria Chudnovsky
AU  - Julien Codsi
AU  - Ajaykrishnan E S
AU  - Daniel Lokshtanov
AU  - Ilya Maier
PY  - 2026
DA  - 2026/10/20
PB  - arXiv
DO  - 10.48550/arxiv.2610.28865
UR  - https://arxiv.org/abs/2610.28865
AB  - A three-path-configuration is a graph consisting of three pairwise internally vertex-disjoint paths, the union of every two of which is an induced cycle of length at least four. A graph is 3PC-free if no induced subgraph of it is a three-path-configuration. We show that 3PC-free graphs have logarithmic tree-independence number, which is asymptotically best possible.
ER  -