Embedding graphs having Ore-degree at most five

DOI10.1137/17M1155442MaRDI QIDQ3119788zbMATH OpenOpenAlexWikidataFDO

Authors Béla Csaba, Judit Nagy-György

Publication date 13 March 2019

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

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

zbMATH Keywords

Bollobás-Eldridge-Catlin conjectureembedding problemsOre-degree

Mathematics Subject Classification ID

Vertex degrees (05C07) Extremal problems in graph theory (05C35) Structural characterization of families of graphs (05C75) Graph theory (including graph drawing) in computer science (68R10)

Abstract: Let $H$ and $G$ be graphs on $n$ vertices, where $n$ is sufficiently large. We prove that if $H$ has Ore-degree at most 5 and $G$ has minimum degree at least $2n/3$ then $HsubsetG.$

Recommendations

• An Ore-type theorem for perfect packings in graphs
• Embedding Arbitrary Graphs of Maximum Degree Two
• The minimum degree threshold for perfect graph packings
• Forcing spanning subgraphs via Ore type conditions
• Hypergraph Packing and Graph Embedding

Cites work

• 2-factors in dense graphs
• An algorithmic version of the blow-up lemma
• An Ore-type analogue of the Sauer-Spencer theorem
• An Ore-type theorem on equitable coloring
• An Ore-type theorem on Hamiltonian square cycles
• Approximate multipartite version of the Hajnal-Szemerédi theorem
• Blow-up lemma
• Edge disjoint placement of graphs
• Embedding Arbitrary Graphs of Maximum Degree Two
• Extremal graph packing problems: Ore-type versus Dirac-type
• Graphs containing every 2-factor
• Hamiltonian square-paths
• scientific article; zbMATH DE number 3641497 (Why is no real title available?)
• scientific article; zbMATH DE number 1528185 (Why is no real title available?)
• scientific article; zbMATH DE number 878896 (Why is no real title available?)
• Note on Hamilton Circuits
• On the bipartite graph packing problem
• On the Bollobás–Eldridge Conjecture for Bipartite Graphs
• On the maximal number of independent circuits in a graph
• Ore-degree threshold for the square of a Hamiltonian cycle
• Ore-type graph packing problems
• Packings of graphs and applications to computational complexity
• Proof of a conjecture of Bollobás and Eldridge for graphs of maximum degree three
• Some Theorems on Abstract Graphs
• The probabilistic method. With an appendix on the life and work of Paul Erdős.

Cited in

(4)

• An Ore-type theorem for perfect packings in graphs
• Bounding the number of embeddings of 5-connected projective-planar graphs
• Embeddings of N₅ and the contiguous degrees
• On embedding well-separable graphs

This page was built for publication: Embedding graphs having Ore-degree at most five

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