TY - JOUR

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

AU - Kostochka, Alexandr

AU - Stocker, Christopher

AU - Hamburger, Peter

PY - 2013/10

Y1 - 2013/10

N2 - 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.

AB - 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.

KW - graph packing

KW - hypergraph

UR - http://www.scopus.com/inward/record.url?scp=84881480114&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84881480114&partnerID=8YFLogxK

U2 - 10.1002/jgt.21706

DO - 10.1002/jgt.21706

M3 - Article

AN - SCOPUS:84881480114

VL - 74

SP - 222

EP - 235

JO - Journal of Graph Theory

JF - Journal of Graph Theory

SN - 0364-9024

IS - 2

ER -