A randomized embedding algorithm for trees

DOI10.1007/s00493-010-2422-5zbMath1231.05274OpenAlexW1988204800MaRDI QIDQ555509

Jan Vondrák, Benjamin Sudakov

Publication date: 22 July 2011

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00493-010-2422-5

zbMATH Keywords

randomized algorithm\(C_4\)-free graphs\(K_{s,t}\)-free graphsembedding a tree to a graphgraphs of fixed girth

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Random walks on graphs (05C81)

Related Items

An approximate version of Sumner's universal tournament conjecture, Embedding Spanning Bipartite Graphs of Small Bandwidth, Expanders Are Universal for the Class of All Spanning Trees, A geometric theory for hypergraph matching, Unnamed Item, Percolation on Random Graphs with a Fixed Degree Sequence, The Approximate Loebl--Komlós--Sós Conjecture I: The Sparse Decomposition

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Cycle lengths in sparse graphs
• Embedding nearly-spanning bounded degree trees
• Minors in expanding graphs
• Expanding graphs contain all small trees
• Trees in sparse random graphs
• Hamiltonian circuits in random graphs
• Norm-graphs: Variations and applications
• Markov chains indexed by trees
• \(C_ 6\)-free bipartite graphs and product representation of squares
• Every graph with a positive Cheeger constant contains a tree with a positive Cheeger constant
• Embedding trees into graphs of large girth
• On a conjecture about trees in graphs with large girth
• The Erdös-Sós conjecture for graphs of girth 5
• Norm-graphs and bipartite Turán numbers
• Tree embeddings
• Universal Graphs for Bounded-Degree Trees and Planar Graphs
• Four-cycles in graphs without a given even cycle
• Minimal Regular Graphs of Girths Eight and Twelve
• A Note on Bipartite Graphs Without 2 k -Cycles
• On a problem of K. Zarankiewicz
• The size-Ramsey number of trees