Tree-independence number and forbidden induced subgraphs: excluding a $6$-vertex path and a $(2,t)$-biclique
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910097387552768 |
|---|---|
| author | Chudnovsky, Maria Codsi, Julien Gollin, J. Pascal Milanič, Martin Sivashankar, Varun |
| author_facet | Chudnovsky, Maria Codsi, Julien Gollin, J. Pascal Milanič, Martin Sivashankar, Varun |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_01999 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Tree-independence number and forbidden induced subgraphs: excluding a $6$-vertex path and a $(2,t)$-biclique Chudnovsky, Maria Codsi, Julien Gollin, J. Pascal Milanič, Martin Sivashankar, Varun Combinatorics 05C75, 05C40, 05C05 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. |
| title | Tree-independence number and forbidden induced subgraphs: excluding a $6$-vertex path and a $(2,t)$-biclique |
| topic | Combinatorics 05C75, 05C40, 05C05 |
| url | https://arxiv.org/abs/2604.01999 |