On deficiency problems for graphs
Research output: Contribution to journal › Article › peer-review
Colleges, School and Institutes
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.
|Journal||Combinatorics, Probability and Computing|
|Early online date||27 Sep 2021|
|Publication status||E-pub ahead of print - 27 Sep 2021|
- graph deficiency, clique factors, bandwidth theorems