Covering 3‐uniform hypergraphs by vertex‐disjoint tight paths

DOI10.1002/JGT.22853MaRDI QIDQ6046654zbMATH OpenOpenAlexFDO

Authors

Publication date 5 October 2023

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

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

zbMATH Keywords

Hamilton cycletight path

Mathematics Subject Classification ID

Paths and cycles (05C38) Eulerian and Hamiltonian graphs (05C45) Hypergraphs (05C65)

Abstract: Let $H$ be an $n$-vertex 3-uniform hypergraph such that every pair of vertices is in at least $n/3+o(n)$ edges. We show that $H$ contains two vertex-disjoint tight paths whose union covers the vertex set of $H$. The quantity two here is best possible and the degree condition is asymptotically best possible. This result also has an interpretation as the emph{deficiency problems}, recently introduced by Nenadov, Sudakov and Wagner: every such $H$ can be made Hamiltonian by adding at most two vertices and all triples intersecting them.

Recommendations

• Minimum vertex degree condition for tight Hamiltonian cycles in 3‐uniform hypergraphs
• Packing tight Hamilton cycles in 3-uniform hypergraphs
• Dirac-type conditions for Hamiltonian paths and cycles in 3-uniform hypergraphs
• Packing tight Hamilton cycles in 3-uniform hypergraphs
• Disjoint perfect matchings in 3‐uniform hypergraphs

Cites work

• A Dirac-Type Theorem for 3-Uniform Hypergraphs
• An approximate Dirac-type theorem for k-uniform hypergraphs
• Completion and deficiency problems
• Covering and tiling hypergraphs with tight cycles
• Covering the vertices of a graph by vertex-disjoint paths
• Decision problem for perfect matchings in dense k-uniform hypergraphs
• Dirac-type conditions for Hamiltonian paths and cycles in 3-uniform hypergraphs
• Dirac-type questions for hypergraphs -- a survey (or more problems for Endre to solve)
• Forbidding Hamilton cycles in uniform hypergraphs
• Forcing large tight components in 3-graphs
• Hamilton \(\ell \)-cycles in uniform hypergraphs
• Hamilton cycles in graphs and hypergraphs: an extremal perspective
• Hamiltonian chains in hypergraphs
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• Hypergraphs, quasi-randomness, and conditions for regularity
• Loose Hamiltonian cycles forced by large (k-2)-degree-approximate version
• Minimum codegree threshold for \(C_6^3\)-factors in 3-uniform hypergraphs
• Minimum codegree threshold for Hamilton \(\ell\)-cycles in \(k\)-uniform hypergraphs
• Minimum vertex degree condition for tight Hamiltonian cycles in 3‐uniform hypergraphs
• Minimum vertex degree threshold for loose Hamilton cycles in 3-uniform hypergraphs
• On extremal hypergraphs for Hamiltonian cycles
• On extremal problems of graphs and generalized graphs
• The complexity of perfect matchings and packings in dense hypergraphs
• The Hamiltonian problem and \(t\)-path traceable graphs
• The Ramsey number for 3-uniform tight hypergraph cycles
• Tight cycles and regular slices in dense hypergraphs

Cited in

(3)

• Embedding coverings of 2-paths with 3-paths
• Codegree thresholds for covering 3-uniform hypergraphs
• Non-linear Hamilton cycles in linear quasirandom and uniformly dense hypergraphs

This page was built for publication: Covering 3‐uniform hypergraphs by vertex‐disjoint tight paths

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