Embedding into Bipartite Graphs

DOI10.1137/090765481MaRDI QIDQ3013126zbMATH OpenOpenAlexFDO

Authors Julia Böttcher, Peter Heinig, Anusch Taraz

Publication date 18 July 2011

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

extremal combinatoricsgraph embeddinggraph theory

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: The conjecture of Bollob'as and Koml'os, recently proved by B"ottcher, Schacht, and Taraz [Math. Ann. 343(1), 175--205, 2009], implies that for any $gamma>0$, every balanced bipartite graph on $2n$ vertices with bounded degree and sublinear bandwidth appears as a subgraph of any $2n$-vertex graph $G$ with minimum degree $(1+gamma)n$, provided that $n$ is sufficiently large. We show that this threshold can be cut in half to an essentially best-possible minimum degree of $(frac12+gamma)n$ when we have the additional structural information of the host graph $G$ being balanced bipartite. This complements results of Zhao [to appear in SIAM J. Discrete Math.], as well as Hladk'y and Schacht [to appear in SIAM J. Discrete Math.], who determined a corresponding minimum degree threshold for $K_{r,s}$-factors, with $r$ and $s$ fixed. Moreover, it implies that the set of Hamilton cycles of $G$ is a generating system for its cycle space.

Recommendations

• scientific article; zbMATH DE number 51713
• Embeddings of graphs
• Embedding Graphs into Embedded Graphs
• Embedding graphs into embedded graphs
• scientific article; zbMATH DE number 4164896
• Regular embeddings of complete bipartite graphs
• scientific article; zbMATH DE number 951476
• scientific article; zbMATH DE number 1933239
• A remark on embedded bipartite graphs
• scientific article; zbMATH DE number 4135963

Cited in

(13)

• How tight is the Bollobás-Komlós conjecture?
• Bipartite Ramsey numbers for graphs of small bandwidth
• \(p\)-arrangeable graphs are Folkman linear
• Ramsey numbers of large books and bipartite graphs with small bandwidth
• Embedding graphs into embedded graphs
• Ramsey numbers for bipartite graphs with small bandwidth
• On prisms, Möbius ladders and the cycle space of dense graphs
• Three-color Ramsey number of an odd cycle versus bipartite graphs with small bandwidth
• scientific article; zbMATH DE number 1933239 (Why is no real title available?)
• Three-Color Bipartite Ramsey Number for Graphs with Small Bandwidth
• Embedding spanning bipartite graphs of small bandwidth
• Embedding Graphs into Embedded Graphs
• Packing large balanced trees into bipartite graphs

This page was built for publication: Embedding into Bipartite Graphs

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