

























In an $r$-partite graph, an independent transversal of size $s$ (ITS) consists of $s$ vertices from each part forming an independent set. Motivated by a question from Bollobás, Erdős, and Szemerédi (1975), Di Braccio and Illingworth (2024) inquired about the minimum degree needed to ensure an $n \times \cdots \times n$ $r$-partite graph contains $K_r(s)$, a complete $r$-partite graph with $s$ vertices in each part. We reformulate this as finding the smallest $n$ such that any $n \times \cdots \times n$ $r$-partite graph with maximum degree $Δ$ has an ITS. For any $\varepsilon>0$, we prove the existence of a $γ>0$ ensuring that if $G$ is a multipartite graph partitioned as $(V_1, V_2, \ldots, V_r)$, where the average degree of each part $V_i$ is at most $D$, the maximum degree of any vertex to any part $V_i$ is at most $γD$, and the size of each part $V_i$ is at least $(s + \varepsilon)D$, then $G$ possesses an ITS. The constraint $(s + \varepsilon)D$ on the part size is tight. This extends results of Loh and Sudakov (2007), Glock and Sudakov (2022), and Kang and Kelly (2022). We also show that any $n \times \cdots \times n$ $r$-partite graph with minimum degree at least $\left(r-1-\frac{1}{2s^2}\right)n$ contains $K_r(s)$ and provide a relative Turán-type result. Additionally, this paper explores counting ITSs in multipartite graphs.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。