A hypergraph version of a graph packing theorem by Bollobás and Eldridge

Alexandr Kostochka, Christopher Stocker, Peter Hamburger

Research output: Contribution to journalArticlepeer-review

Abstract

Two n-vertex hypergraphs G and H pack, if there is a bijection f:V(G)→V(H) such that for every edge eâ̂̂E(G), the set {f(v):vâ̂̂e} is not an edge in H. Extending a theorem by Bollobás and Eldridge on graph packing to hypergraphs, we show that if n≥10 and n-vertex hypergraphs G and H with |E(G)|+|E(H)|≤2n-3 with no edges of size 0, 1, n-1 and n do not pack, then either one of G and H contains a spanning graph-star, and each vertex of the other is contained in a graph edge, or one of G and H has n-1 edges of size n-2 not containing a given vertex, and for every vertex x of the other hypergraph some edge of size n-2 does not contain x.

Original languageEnglish (US)
Pages (from-to)222-235
Number of pages14
JournalJournal of Graph Theory
Volume74
Issue number2
DOIs
StatePublished - Oct 2013

Keywords

  • graph packing
  • hypergraph

ASJC Scopus subject areas

  • Geometry and Topology

Fingerprint

Dive into the research topics of 'A hypergraph version of a graph packing theorem by Bollobás and Eldridge'. Together they form a unique fingerprint.

Cite this