Spanning trees in dense graphs
From MaRDI portal
The paper proves the following, almost optimal result: For any \(\delta > 0,\) there exist constants \(c\) and \(n_0\) such that, if \(n \geq n_0,\) \(T\) is a tree of order \(n\) and maximum degree at most \(cn/\log n,\) and graph \(G\) of order \(n\) has minimum degree at least \((1/2+\delta)n,\) then \(T\) is a subgraph of \(G.\) The proof is based on the regularity lemma/blow-up lemma method. One of the main merits is: this is the first case where this proof method was applicable for finding spanning subgraphs with higher than constant maximum degree.
Recommendations
Cited in
(39)- Spanning trees in multipartite geometric graphs
- Star-factors in graphs with large minimum degree
- Random perturbation of sparse graphs
- Emerging spanning trees in the work of Candilis-Josic-Woods
- Spanning trees of dense directed graphs
- On the bipartite graph packing problem
- Spanning trees in dense directed graphs
- Spanning embeddings of arrangeable graphs with sublinear bandwidth
- Bounded-Degree Spanning Trees in Randomly Perturbed Graphs
- Embedding Graphs into Larger Graphs: Results, Methods, and Problems
- Embedding large subgraphs into dense graphs
- A blow-up lemma for approximate decompositions
- Tree decompositions of graphs without large bipartite holes
- Universality for bounded degree spanning trees in randomly perturbed graphs
- An edge-swap heuristic for finding dense spanning trees
- Degree conditions for embedding trees
- The approximate Loebl-Komlós-Sós conjecture. I: The sparse decomposition
- Bandwidth, treewidth, separators, expansion, and universality
- Existence of spanning \(\mathcal{F}\)-free subgraphs with large minimum degree
- Expanders are universal for the class of all spanning trees
- Transversal factors and spanning trees
- Spanning trees in graphs of high minimum degree with a universal vertex I: An asymptotic result
- Spanning trees in graphs of high minimum degree with a universal vertex II: A tight result
- Dirac-type conditions for spanning bounded-degree hypertrees
- Embedding loose spanning trees in 3-uniform hypergraphs
- Counting oriented trees in digraphs with large minimum semidegree
- A proof of the Elliott-Rödl conjecture on hypertrees in Steiner triple systems
- Spanning trees in graphs without large bipartite holes
- Counting spanning subgraphs in dense hypergraphs
- Stability of transversal Hamilton cycles and paths
- Transversal panconnectedness in graph collections
- Creating spanning trees in Waiter-Client games
- Packing large balanced trees into bipartite graphs
- Dirac's theorem for linear hypergraphs
- Randomly perturbed digraphs also have bounded-degree spanning trees
- Transversal Hamilton paths and cycles
- Spanning 3-colourable subgraphs of small bandwidth in dense graphs
- On embedding well-separable graphs
- Proof of the bandwidth conjecture of Bollobás and Komlós
This page was built for publication: Spanning trees in dense graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2777891)
