EMBEDDING SPANNING BOUNDED DEGREE GRAPHS IN RANDOMLY PERTURBED GRAPHS

DOI10.1112/MTK.12005MaRDI QIDQ5112840zbMATH OpenOpenAlexFDO

Authors Julia Böttcher, Richard Montgomery, Yury Person, O. Parczyk

Publication date 9 June 2020

Published in Mathematika (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1112/mtk.12005

zbMATH Keywords

randomly perturbed dense graphs

Mathematics Subject Classification ID

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

Recommendations

• Embedding spanning bounded degree subgraphs in randomly perturbed graphs
• Embedding graphs with bounded degree in sparse pseudorandom graphs
• Bounded-Degree Spanning Trees in Randomly Perturbed Graphs
• Embedding spanning trees in random graphs
• Embedding spanning subgraphs in uniformly dense and inseparable graphs
• Embeddings of graphs of fixed treewidth and bounded degree
• Universality for bounded degree spanning trees in randomly perturbed graphs
• Spanning trees in randomly perturbed graphs
• On the stretch factor of randomly embedded random graphs
• On embedding graphs with bounded sum of size and maximum degree

Cites work

• Hall's theorem for hypergraphs

Cited in

(27)

• Tilings in randomly perturbed dense graphs
• The bandwidth theorem for locally dense graphs
• High powers of Hamiltonian cycles in randomly augmented graphs
• The square of a Hamilton cycle in randomly perturbed graphs
• Powers of Hamilton cycles in dense graphs perturbed by a random geometric graph
• Embedding loose spanning trees in 3-uniform hypergraphs
• Large Rainbow Cliques in Randomly Perturbed Dense Graphs
• Hamiltonicity of graphs perturbed by a random geometric graph
• Bounded-Degree Spanning Trees in Randomly Perturbed Graphs
• Rainbow trees in uniformly edge‐colored graphs
• Universality for bounded degree spanning trees in randomly perturbed graphs
• Rainbow Hamilton cycles in randomly colored randomly perturbed dense graphs
• Vertex Ramsey properties of randomly perturbed graphs
• Random perturbation of sparse graphs
• Hamiltonicity of graphs perturbed by a random regular graph
• Tilings in randomly perturbed graphs: Bridging the gap between Hajnal‐Szemerédi and Johansson‐Kahn‐Vu
• Triangles in randomly perturbed graphs
• Very fast construction of bounded‐degree spanning graphs via the semi‐random graph process
• Embedding large graphs into a random graph
• On powers of tight Hamilton cycles in randomly perturbed hypergraphs
• Ramsey properties of randomly perturbed graphs: cliques and cycles
• Uniform linear embeddings of spatial random graphs
• Small rainbow cliques in randomly perturbed dense graphs
• Speeding up random walk mixing by starting from a uniform vertex
• Factors in randomly perturbed hypergraphs
• Dirac-type conditions for spanning bounded-degree hypertrees
• Embedding spanning bounded degree subgraphs in randomly perturbed graphs

This page was built for publication: EMBEDDING SPANNING BOUNDED DEGREE GRAPHS IN RANDOMLY PERTURBED GRAPHS

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5112840)