ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2019: 0.755

SCImago Journal Rank (SJR) 2019: 0.600

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory


Discussiones Mathematicae Graph Theory 29(3) (2009) 651-656
DOI: 10.7151/dmgt.1471


Paweł Naroski

Faculty of Mathematics and Information Science
Warsaw University of Technology
Pl. Politechniki 1, 00-661 Warsaw, Poland


Hypergraphs H1,...,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.

Keywords: nonuniform hypergraph, packing.

2000 Mathematics Subject Classification: 05C65, 05C70, 05D05.


[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.
[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.
[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.
[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.
[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.
[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.
[7] M. Woźniak, Embedding graphs of small size, Discrete Appl. Math. 51 (1994) 233-241, doi: 10.1016/0166-218X(94)90112-0.
[8] M. Woźniak, Packing of graphs, Dissertationes Math. 362 (1997) 1-78.
[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.
[10] H.P. Yap, Packing of graphs - a survey, Discrete Math. 72 (1988) 395-404, doi: 10.1016/0012-365X(88)90232-4.

Received 7 May 2008
Revised 12 August 2008
Accepted 30 September 2008