No CrossRef data available.
Article contents
Spanning trees in graphs without large bipartite holes
Published online by Cambridge University Press: 14 November 2023
Abstract
We show that for any $\varepsilon \gt 0$ and
$\Delta \in \mathbb{N}$, there exists
$\alpha \gt 0$ such that for sufficiently large
$n$, every
$n$-vertex graph
$G$ satisfying that
$\delta (G)\geq \varepsilon n$ and
$e(X, Y)\gt 0$ for every pair of disjoint vertex sets
$X, Y\subseteq V(G)$ of size
$\alpha n$ contains all spanning trees with maximum degree at most
$\Delta$. This strengthens a result of Böttcher, Han, Kohayakawa, Montgomery, Parczyk, and Person.
- Type
- Paper
- Information
- Copyright
- © The Author(s), 2023. Published by Cambridge University Press
Footnotes
Jie Hu: Supported by Natural Science Foundation of China (12131013, 12161141006). Guanghui Wang: Research supported by Natural Science Foundation of China (12231018) and Young Taishan Scholars probgram of Shandong Province (201909001). Donglei Yang: Supported by the China Post-doctoral Science Foundation (2021T140413), Natural Science Foundation of China (12101365) and Natural ScienceFoundation of Shandong Province (ZR2021QA029).
References
![](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20240404180551619-0507:S0963548323000378:S0963548323000378_inline1366.png?pub-status=live)
![](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20240404180551619-0507:S0963548323000378:S0963548323000378_inline1367.png?pub-status=live)
![](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20240404180551619-0507:S0963548323000378:S0963548323000378_inline1368.png?pub-status=live)
![](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20240404180551619-0507:S0963548323000378:S0963548323000378_inline1369.png?pub-status=live)
![](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20240404180551619-0507:S0963548323000378:S0963548323000378_inline1370.png?pub-status=live)
![](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20240404180551619-0507:S0963548323000378:S0963548323000378_inline1371.png?pub-status=live)