×

On a conjecture about trees in graphs with large girth. (English) Zbl 1023.05035

Summary: The girth of a graph \(G\) is the length of a shortest cycle in G. E. Dobson [Ph.D. dissertation, Louisiana State University, Baton Rouge, LA (1994)] conjectured that ever graph \(G\) with girth at least \(2t+1\) and minimum degree at least \(k/t\) contains every tree \(T\) with \(k\) edges whose maximum degree does not exceed the minimum degree of \(G\). The conjecture has been proved for \(t\leq 3\). In this paper, we prove Dobson’s conjecture.

MSC:

05C05 Trees
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Brandt, S.; Dobson, E., The Erdős-Sós conjecture for graphs of girth 5, Discrete Math., 150, 411-414 (1996) · Zbl 0854.05064
[2] E. Dobson, Ph.D. dissertation, Louisiana State University, Baton Rouge, LA, 1995.; E. Dobson, Ph.D. dissertation, Louisiana State University, Baton Rouge, LA, 1995.
[3] Haxell, P.; Luczak, T., Embedding trees into graphs of large girth, Discrete Math., 216, 273-278 (2000) · Zbl 0958.05030
[4] Saclé, J.-F.; Woźniak, M., A note on the Erdős-Sós conjecture for graphs without \(C_4\), J. Combin. Theory Ser. B, 70, 367-372 (1997) · Zbl 0878.05024
[5] Saclé, J.-F.; Woźniak, M., On graphs which contain each tree of given size, Discrete Math., 165/166, 599-605 (1997) · Zbl 0876.05018
[6] Soffer, S. N., The Komlós-Sós conjecture for graphs of girth 7, Discrete Math., 214, 279-283 (2000) · Zbl 0946.05027
[7] West, D. B., Introduction to Graph Theory (1996), Prentice-Hall: Prentice-Hall New Jersey · Zbl 0845.05001
[8] Woźniak, M., On the Erdős-Sós conjecture, J. Graph Theory, 21, 229-234 (1996) · Zbl 0841.05017
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.