Universality of random graphs and rainbow embedding

DOI10.1002/rsa.20596zbMath1338.05248arXiv1311.7063OpenAlexW1951087126WikidataQ105583249 ScholiaQ105583249MaRDI QIDQ2811163

Ueli Peter, Asaf Ferber, Rajko Nenadov

Publication date: 10 June 2016

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1311.7063

zbMATH Keywords

random graphsembeddingsuniversality

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items

On rainbow Hamilton cycles in random hypergraphs, Spanning structures and universality in sparse hypergraphs, The threshold for the full perfect matching color profile in a random coloring of random graphs, Embedding Graphs into Larger Graphs: Results, Methods, and Problems, Almost‐spanning universality in random graphs, Optimal threshold for a random graph to be 2-universal, The Approximate Loebl--Komlós--Sós Conjecture I: The Sparse Decomposition

Cites Work

• Embedding nearly-spanning bounded degree trees
• Bandwidth, expansion, treewidth, separators and universality for bounded-degree graphs
• Spanning subgraphs of random graphs
• Matching and covering the vertices of a random graph by copies of a given graph
• Sparse universal graphs
• Large bounded degree trees in expanding graphs
• Universality of Random Graphs for Graphs of Maximum Degree Two
• Explicit sparse almost-universal graphs for ${\bf {{\cal G}(n, {k \over n})}}$
• Local resilience of almost spanning trees in random graphs
• Multi-Coloured Hamilton Cycles in Random Edge-Coloured Graphs
• Factors in random graphs
• Universal Graphs for Bounded-Degree Trees and Planar Graphs
• On Graphs Which Contain All Sparse Graphs
• On Universal Graphs for Spanning Trees
• Expanders Are Universal for the Class of All Spanning Trees
• Rainbow hamilton cycles in random graphs
• Sparse universal graphs for bounded‐degree graphs
• Concentration of Measure for the Analysis of Randomized Algorithms