Reconfiguration of Independent Transversals
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909243188183040 |
|---|---|
| author | Buys, Pjotr Kang, Ross J. Ozeki, Kenta |
| author_facet | Buys, Pjotr Kang, Ross J. Ozeki, Kenta |
| contents | Given integers $Δ\ge 2$ and $t\ge 2Δ$, suppose there is a graph of maximum degree $Δ$ and a partition of its vertices into blocks of size at least $t$. By a seminal result of Haxell, there must be some independent set of the graph that is transversal to the blocks, a so-called independent transversal. We show that, if moreover $t\ge2Δ+1$, then every independent transversal can be transformed within the space of independent transversals to any other through a sequence of one-vertex modifications, showing connectivity of the so-called reconfigurability graph of independent transversals.
This is sharp in that for $t=2Δ$ (and $Δ\ge 2$) the connectivity conclusion can fail. In this case we show furthermore that in an essential sense it can only fail for the disjoint union of copies of the complete bipartite graph $K_{Δ,Δ}$. This constitutes a qualitative strengthening of Haxell's theorem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_04367 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Reconfiguration of Independent Transversals Buys, Pjotr Kang, Ross J. Ozeki, Kenta Combinatorics Data Structures and Algorithms 05C35, 05C69, 05C15, 68R05, 68R10 Given integers $Δ\ge 2$ and $t\ge 2Δ$, suppose there is a graph of maximum degree $Δ$ and a partition of its vertices into blocks of size at least $t$. By a seminal result of Haxell, there must be some independent set of the graph that is transversal to the blocks, a so-called independent transversal. We show that, if moreover $t\ge2Δ+1$, then every independent transversal can be transformed within the space of independent transversals to any other through a sequence of one-vertex modifications, showing connectivity of the so-called reconfigurability graph of independent transversals. This is sharp in that for $t=2Δ$ (and $Δ\ge 2$) the connectivity conclusion can fail. In this case we show furthermore that in an essential sense it can only fail for the disjoint union of copies of the complete bipartite graph $K_{Δ,Δ}$. This constitutes a qualitative strengthening of Haxell's theorem. |
| title | Reconfiguration of Independent Transversals |
| topic | Combinatorics Data Structures and Algorithms 05C35, 05C69, 05C15, 68R05, 68R10 |
| url | https://arxiv.org/abs/2407.04367 |