Approximate packing of independent transversals in locally sparse graphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866912503145955328 |
|---|---|
| author | Chakraborti, Debsoumya Tran, Tuan |
| author_facet | Chakraborti, Debsoumya Tran, Tuan |
| contents | Fix $\varepsilon >0$ and consider a multipartite graph $G$ with maximum degree at most $(1-\varepsilon)n$, parts $V_1,\ldots,V_k$ of the same size $n$, and where every vertex has at most $o(n)$ neighbors in any part $V_i$. Loh and Sudakov proved that any such $G$ has an independent transversal. They further conjectured that the vertex set of $G$ can be decomposed into pairwise disjoint independent transversals. In the present paper, we resolve this conjecture approximately by showing that $G$ contains $(1-\varepsilon)n$ pairwise disjoint independent transversals. As applications, we give approximate answers to questions of Yuster, and of Fischer, Kühn, and Osthus. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_02815 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Approximate packing of independent transversals in locally sparse graphs Chakraborti, Debsoumya Tran, Tuan Combinatorics Fix $\varepsilon >0$ and consider a multipartite graph $G$ with maximum degree at most $(1-\varepsilon)n$, parts $V_1,\ldots,V_k$ of the same size $n$, and where every vertex has at most $o(n)$ neighbors in any part $V_i$. Loh and Sudakov proved that any such $G$ has an independent transversal. They further conjectured that the vertex set of $G$ can be decomposed into pairwise disjoint independent transversals. In the present paper, we resolve this conjecture approximately by showing that $G$ contains $(1-\varepsilon)n$ pairwise disjoint independent transversals. As applications, we give approximate answers to questions of Yuster, and of Fischer, Kühn, and Osthus. |
| title | Approximate packing of independent transversals in locally sparse graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2402.02815 |