The Library
On deficiency problems for graphs
Tools
Freschi, Andrea, Hyde, Joseph and Treglown, Andrew (2022) On deficiency problems for graphs. Combinatorics, Probability and Computing, 31 (3). pp. 478-488. doi:10.1017/S0963548321000389 ISSN 0963-5483.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1017/S0963548321000389
Abstract
Motivated by analogous questions in the setting of Steiner triple systems and Latin squares, Nenadov, Sudakov and Wagner [Completion and deficiency problems, Journal of Combinatorial Theory Series B, 2020] recently introduced the notion of graph deficiency. Given a global spanning property P and a graph G , the deficiency def(G) of the graph G with respect to the property P is the smallest non-negative integer t such that the join G∗Kt has property P . In particular, Nenadov, Sudakov and Wagner raised the question of determining how many edges an n-vertex graph G needs to ensure G∗Kt contains a Kr -factor (for any fixed r≥3 ). In this paper, we resolve their problem fully. We also give an analogous result that forces G∗Kt to contain any fixed bipartite (n+t) -vertex graph of bounded degree and small bandwidth.
Item Type: | Journal Article | ||||||||
---|---|---|---|---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||||||
Journal or Publication Title: | Combinatorics, Probability and Computing | ||||||||
Publisher: | Cambridge University Press | ||||||||
ISSN: | 0963-5483 | ||||||||
Official Date: | May 2022 | ||||||||
Dates: |
|
||||||||
Volume: | 31 | ||||||||
Number: | 3 | ||||||||
Page Range: | pp. 478-488 | ||||||||
DOI: | 10.1017/S0963548321000389 | ||||||||
Status: | Peer Reviewed | ||||||||
Publication Status: | Published | ||||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||||
Copyright Holders: | © The Author(s), 2021. Published by Cambridge University Press |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |