Hostname: page-component-74656f9884-8r8nv Total loading time: 0 Render date: 2026-11-09T18:17:46.312Z Has data issue: false hasContentIssue false
  • English
  • Français

Existence of Spanning ℱ-Free Subgraphs with Large Minimum Degree

Part of: Graph theory Extremal combinatorics

Published online by Cambridge University Press:  07 December 2016

G. PERARNAU  and
B. REED
G. PERARNAU
Affiliation:
School of Mathematics, University of Birmingham, United Kingdom (e-mail: g.perarnau@bham.ac.uk)
B. REED
Affiliation:
School of Computer Science, McGill University, Canada and Kawarabayashi Large Graph Project, National Institute of Informatics, Japan (e-mail: breed@mcgill.ca)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Let ℱ be a family of graphs and let d be large enough. For every d-regular graph G, we study the existence of a spanning ℱ-free subgraph of G with large minimum degree. This problem is well understood if ℱ does not contain bipartite graphs. Here we provide asymptotically tight results for many families of bipartite graphs such as cycles or complete bipartite graphs. To prove these results, we study a locally injective analogue of the question.

MSC classification

Primary: 05C35: Extremal problems
Secondary: 05D40: Probabilistic methods

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 26 , Issue 3 , May 2017 , pp. 448 - 467
Copyright
Copyright © Cambridge University Press 2016 

References

[1] Alon, N., Rónyai, L. and Szabó, T. (1999) Norm-graphs: Variations and applications. J. Combin. Theory Ser. B 76 280–290.Google Scholar
[2] Brown, W. G. (1966) On graphs that do not contain a Thomsen graph. Canad. Math. Bull. 9 1–2.CrossRefGoogle Scholar
[3] Conlon, D., Fox, J. and Sudakov, B. (2016) Short proofs of some extremal results II. J. Combin. Theory Ser. B 121 173–196.Google Scholar
[4] Delcourt, M. and Ferber, A. (2015) On a conjecture of Thomassen. Electron. J. Combin. 22 P3.2.Google Scholar
[5] Erdős, P. (1959) Graph theory and probability I. Canad. J. Math. 11 34–38.CrossRefGoogle Scholar
[6] Erdős, P. (1961) Graph theory and probability II. Canad. J. Math. 13 346–352.Google Scholar
[7] Erdős, P. (1968) Problem 1. In Theory of Graphs: Proc. Colloq. Tihany 1966, Academic Press, pp. 361–362.Google Scholar
[8] Erdős, P., Rényi, A. and Sós, V. T. (1966) On a problem of graph theory. Studia Sci. Math. Hungar. 1 215–235.Google Scholar
[9] Erdős, P. and Simonovits, M. (1970) Some extremal problems in graph theory. In Combinatorial Theory and its Applications, I: Proc. Colloq., Balatonfüred, 1969, North-Holland, pp. 377–390.Google Scholar
[10] Foucaud, F., Krivelevich, M. and Perarnau, G. (2015) Large subgraphs without short cycles. SIAM J. Discrete Math. 29 65–78.Google Scholar
[11] Füredi, Z. and Simonovits, M. (2013) The history of degenerate (bipartite) extremal graph problems. In Erdős Centennial, Vol. 25 of Bolyai Society Mathematical Studies, Springer, pp. 169–264.Google Scholar
[12] Kollár, J., Rónyai, L. and Szabó, T. (1996) Norm-graphs and bipartite Turán numbers. Combinatorica 16 399–406.Google Scholar
[13] Kővári, T., Sós, V. T. and Turán, P. (1954) On a problem of K. Zarankiewicz. Colloquium Math. 3 50–57.CrossRefGoogle Scholar
[14] Kühn, D. and Osthus, D. (2004) Every graph of sufficiently large average degree contains a C 4-free subgraph of large average degree. Combinatorica 24 155–162.Google Scholar
[15] Kun, G. (2013) Expanders have a spanning Lipschitz subgraph with large girth. arXiv:1303.4982 Google Scholar
[16] Lam, T. and Verstraëte, J. (2005) A note on graphs without short even cycles. Electron. J. Combin. 12 paper 5.CrossRefGoogle Scholar
[17] Lazebnik, F., Ustimenko, V. A. and Woldar, A. J. (1999) Polarities and 2k-cycle-free graphs. Discrete Math. 197 503–513.Google Scholar
[18] Molloy, M. and Reed, B. (2002) Graph Colouring and the Probabilistic Method , Vol. 23 of Algorithms and Combinatorics, Springer.Google Scholar
[19] Thomassen, C. (1983) Girth in graphs. J. Combin. Theory Ser. B 35 129–141.Google Scholar
[20] Thomassen, C. (1989) Configurations in graphs of large minimum degree, connectivity, or chromatic number. Ann. New York Acad. Sci. 555 402–412.CrossRefGoogle Scholar