Tree-independence number and forbidden induced subgraphs: excluding a $6$-vertex path and a $(2,t)$-biclique

Maria Chudnovsky; Julien Codsi; J. Pascal Gollin; Martin Milanič; Varun Sivashankar

Tree-independence number and forbidden induced subgraphs: excluding a $6$-vertex path and a $(2,t)$-biclique

Maria Chudnovsky, Julien Codsi, J. Pascal Gollin, Martin Milanič, Varun Sivashankar

arXivarxiv/2604.01999Apr 2, 2026math.COscore 0

We show that for every positive integer ${t \geq 2}$ there exists an integer $s$ such that every graph that contains no induced subgraph isomorphic to either the $6$-vertex path or the $(2,t)$-biclique, the complete bipartite graph $K_{2,t}$, has tree-independence number at most $s$. This result makes partial progress on a conjecture of Dallard, Krnc, Kwon, Milanič, Munaro, Štorgel, and Wiederrecht.

Source JSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2604.01999
curl -X POST /api/v1/records/arxiv/2604.01999/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2604.01999/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'