A note on some embedding problems for oriented graphs

DOI10.1002/JGT.20586MaRDI QIDQ2891043zbMATH OpenOpenAlexFDO

Authors Andrew Treglown

Publication date 13 June 2012

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1011.4476, http://pure-oai.bham.ac.uk/ws/files/42837303/orientednote.pdf

zbMATH Keywords

Hamilton cyclesoriented graphspackingsRamsey numberstransitive tournaments

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Generalized Ramsey theory (05C55) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: We conjecture that every oriented graph $G$ on $n$ vertices with $delt{a}^{+}(G),delt{a}^{-}(G)geq5n/12$ contains the square of a Hamilton cycle. We also give a conjectural bound on the minimum semidegree which ensures a perfect packing of transitive triangles in an oriented graph. A link between Ramsey numbers and perfect packings of transitive tournaments is also considered.

Recommendations

• Arbitrary orientations of Hamilton cycles in oriented graphs
• Transitive triangle tilings in oriented graphs
• Triangle packings and 1-factors in oriented graphs
• An exact minimum degree condition for Hamilton cycles in oriented graphs
• On directed versions of the Hajnal-Szemerédi theorem

Cites work

• An exact minimum degree condition for Hamilton cycles in oriented graphs
• Decomposition of large combinatorial structures
• Disproof of a conjecture of Erdös and moser on tournaments
• Hamilton Cycles in Oriented Graphs
• scientific article; zbMATH DE number 3149611 (Why is no real title available?)
• On tournaments and their largest transitive subtournaments
• On tournaments free of large transitive subtournaments
• Powers of Hamilton cycles in tournaments
• Proof of the Seymour conjecture for large graphs
• Some Theorems on Abstract Graphs
• Tiling transitive tournaments and their blow-ups
• Triangle packings and 1-factors in oriented graphs

Cited in

(14)

• On ordered graphs and graph orderings
• Transitive triangle tilings in oriented graphs
• Tight bounds for powers of Hamilton cycles in tournaments
• On the restricted isometry property of the Paley matrix
• Cyclic triangle factors in regular tournaments
• Tiling directed graphs with tournaments
• A survey on Hamilton cycles in directed graphs
• On directed versions of the Hajnal-Szemerédi theorem
• Pósa's conjecture for graphs of order at least 2 × 10⁸
• Transitive tournament tilings in oriented graphs with large minimum total degree
• A note between transitive C₄-factor and oriented Ramsey number
• A generalization of the Hamiltonian cycle in dense digraphs
• TT₃-factors in oriented graphs with low independence number
• A note on an embedding problem in transitive tournaments

This page was built for publication: A note on some embedding problems for oriented graphs

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