Packing of nonuniform hypergraphs - product and sum of sizes conditions
Paweł Naroski
Discussiones Mathematicae Graph Theory, Tome 29 (2009), p. 651-656 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

Hypergraphs H₁,...,HN of order n are mutually packable if one can find their edge disjoint copies in the complete hypergraph of order n. We prove that two hypergraphs are mutually packable if the product of their sizes satisfies some upper bound. Moreover we show that an arbitrary set of the hypergraphs is mutually packable if the sum of their sizes is sufficiently small.

Publié le : 2009-01-01
EUDML-ID : urn:eudml:doc:270789 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1471,
     author = {Pawe\l\ Naroski},
     title = {Packing of nonuniform hypergraphs - product and sum of sizes conditions},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {29},
     year = {2009},
     pages = {651-656},
     zbl = {1194.05112},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1471}
}

Paweł Naroski. Packing of nonuniform hypergraphs - product and sum of sizes conditions. Discussiones Mathematicae Graph Theory, Tome 29 (2009) pp. 651-656. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1471/

[000] [1] D. Burns and S. Schuster, Every (p,p-2) graph is contained in its complement, J. Graph Theory 1 (1977) 277-279, doi: 10.1002/jgt.3190010308. | Zbl 0375.05046

[001] [2] D. Burns and S. Schuster, Embeddings (p,p-1) graphs in their complements, Israel J. Math. 4, 30 (1978) 313-320, doi: 10.1007/BF02761996. | Zbl 0379.05023

[002] [3] M. Pilśniak and M. Woźniak, A note on packing of two copies of a hypergraph, Discuss. Math. Graph Theory 27 (2007) 45-49, doi: 10.7151/dmgt.1343. | Zbl 1133.05064

[003] [4] V. Rödl, A. Ruciński and A. Taraz, Hypergraph packing and graph embedding, Combinatorics, Probability and Computing 8 (1999) 363-376, doi: 10.1017/S0963548399003879. | Zbl 0938.05046

[004] [5] N. Sauer and J. Spencer, Edge disjoint placements of graphs, J. Combin. Theory (B) 25 (1978) 295-302, doi: 10.1016/0095-8956(78)90005-9. | Zbl 0417.05037

[005] [6] S. Schuster, Fixed-point-free embeddings of graphs in their complements, Internat. J. Math. & Math. Sci. 1 (1978) 335-338, doi: 10.1155/S0161171278000356. | Zbl 0391.05047

[006] [7] M. Woźniak, Embedding graphs of small size, Discrete Appl. Math. 51 (1994) 233-241, doi: 10.1016/0166-218X(94)90112-0. | Zbl 0807.05025

[007] [8] M. Woźniak, Packing of graphs, Dissertationes Math. 362 (1997) 1-78.

[008] [9] M. Woźniak, Packing of graphs and permutations - a survey, Discrete Math. 276 (2004) 379-391, doi: 10.1016/S0012-365X(03)00296-6. | Zbl 1031.05041

[009] [10] H.P. Yap, Packing of graphs - a survey, Discrete Math. 72 (1988) 395-404, doi: 10.1016/0012-365X(88)90232-4. | Zbl 0685.05036