| Naslov: | Induced matching treewidth and tree-independence number, revisited |
|---|
| Avtorji: | ID Alon, Noga (Avtor)
ID Milanič, Martin (Avtor)
ID Rzążewski, Paweł (Avtor) |
|---|
| Datoteke: |  RAZ_Alon_Noga_2026.pdf (471,21 KB)
MD5: CA1B30FDFCE84EBBED1BD748C7E1C685
 https://www.combinatorics.org/ojs/index.php/eljc/article/view/v33i3p70
|
|---|
| Jezik: | Angleški jezik |
|---|
| Vrsta gradiva: | Članek v reviji |
|---|
| Tipologija: | 1.01 - Izvirni znanstveni članek |
|---|
| Organizacija: | IAM - Inštitut Andrej Marušič
|
|---|
| Opis: | We study two graph parameters defined via tree decompositions: tree-independence number and induced matching treewidth. Both parameters are defined similarly as treewidth, but with respect to different measures of a tree decomposition T of a graph G: for tree-independence number, the measure is the maximum size of an independent set in G included in some bag of T, while for the induced matching treewidth, the measure is the maximum size of an induced matching in G such that some bag of T contains at least one endpoint of every edge of the matching. While the induced matching treewidth of any graph is bounded from above by its tree-independence number, the family of complete bipartite graphs shows that small induced matching treewidth does not imply small tree-independence number. On the other hand, Abrishami, Briański, Czyżewska, McCarty, Milanič, Rzążewski, and Walczak [SIAM Journal on Discrete Mathematics, 2025] showed that, if a fixed biclique K_{t,t} is excluded as an induced subghraph, then the tree-independence number is bounded from above by some function of the induced matching treewidth. The function resulting from their proof is exponential even for fixed t, as it relies on multiple applications of Ramsey’s theorem. In this note we show, using the Kövári-Sós-Turán theorem, that for any class of K_{t,t}-free graphs, the two parameters are in fact polynomially related. |
|---|
| Ključne besede: | tree-independence number, induced matching treewidth, induced biclique, Kövári-Sós-Turán theorem |
|---|
| Verzija publikacije: | Objavljena publikacija |
|---|
| Datum objave: | 11.09.2026 |
|---|
| Leto izida: | 2026 |
|---|
| Št. strani: | str. 1-12 |
|---|
| Številčenje: | Vol. 33, iss. 3, article no. P3.70 |
|---|
| PID: | 20.500.12556/RUP-23630  |
|---|
| UDK: | 519.17 |
|---|
| ISSN pri članku: | 1077-8926 |
|---|
| DOI: | 10.37236/14869 |
|---|
| COBISS.SI-ID: | 291491843 |
|---|
| Datum objave v RUP: | 17.09.2026 |
|---|
| Število ogledov: | 296 |
|---|
| Število prenosov: | 6 |
|---|
| Metapodatki: |    |
|---|
|
:
|
Kopiraj citat |
|---|
| | | | Skupna ocena: | (0 glasov) |
|---|
| Vaša ocena: | Ocenjevanje je dovoljeno samo prijavljenim uporabnikom. |
|---|
| Objavi na: |  |
|---|
Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše
podrobnosti ali sproži prenos. |
