| Naslov: | Tree-independence number of ▫$P_5$▫-free graphs with no large bicliques |
|---|
| Avtorji: | ID Blažej, Václav (Avtor)
ID Gollin, J. Pascal (Avtor)
ID Hons, Tomáš (Avtor)
ID Masařík, Tomáš (Avtor)
ID Milanič, Martin (Avtor)
ID Rzążewski, Paweł (Avtor)
ID Suchý, Ondřej (Avtor)
ID Wesolek, Alexandra (Avtor) |
|---|
| Datoteke: |  RAZ_Blazej_Vaclav_2026.pdf (1,00 MB)
MD5: CE3DBBA8ACDFBDA241E82C898F827AC4
RAZ_Blazej_Vaclav_2026.pdf (1,00 MB)
MD5: CE3DBBA8ACDFBDA241E82C898F827AC4
|
|---|
| Jezik: | Angleški jezik |
|---|
| Vrsta gradiva: | Neznano |
|---|
| Tipologija: | 1.08 - Objavljeni znanstveni prispevek na konferenci |
|---|
| Organizacija: | IAM - Inštitut Andrej Marušič
|
|---|
| Opis: | The tree-independence number of a graph is the minimum, over all tree-decompositions of the graph, of the maximum size of an independent set contained in a bag. Graph classes of bounded tree-independence number have strong structural and algorithmic properties, but the parameter can be unbounded even in quite restricted classes. In particular, the presence of an induced biclique K_{t,t} forces tree-independence number at least t. This leads to the question whether large induced bicliques are the only obstruction to bounded tree-independence number in natural hereditary classes. A conjecture of Dallard, Krnc, Kwon, Milanič, Munaro, Štorgel, and Wiederrecht states that for all positive integers s and t, {P_s,K_{t,t}}-free graphs have bounded tree-independence number. We prove this conjecture for s = 5 by showing that every {P₅,K_{t,t}}-free graph has tree-independence number at most 4t. We also obtain related bounds for the weaker parameter of independence degeneracy. |
|---|
| Ključne besede: | tree-independence number, independence degeneracy, independence treewidth, P5-free graphs |
|---|
| Verzija publikacije: | Objavljena publikacija |
|---|
| Leto izida: | 2026 |
|---|
| Št. strani: | Str. 77:1-77:17 |
|---|
| PID: | 20.500.12556/RUP-23645  |
|---|
| UDK: | 51 |
|---|
| ISSN pri članku: | 1868-8969 |
|---|
| DOI: | 10.4230/LIPIcs.ESA.2026.77 |
|---|
| COBISS.SI-ID: | 291873795 |
|---|
| Datum objave v RUP: | 21.09.2026 |
|---|
| Število ogledov: | 300 |
|---|
| Število prenosov: | 5 |
|---|
| 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. |
