Packing of graphs

Woźniak Mariusz. Packing of graphs. Warszawa: Instytut Matematyczny Polskiej Akademi Nauk, 1997. <http://eudml.org/doc/271750>.

@book{WoźniakMariusz1997,
abstract = {PrefaceThere are two basic reference texts on packing theory: the last chapter of Bollobás's book [6] (1978) and the 4th chapter of Yap's book [85] (1986). They still remain the main references to packing problems. However, many papers related to these problems have recently been published and the reason for writing this survey is to gather in a systematic form results scattered throughout the literature.I wish I could name all who deserve my thanks. I am particularly grateful to A. P. Wojda for introducing me to graph theory, and to Z. Skupień for his interest in my research and for many stimulating conversations.During my work, I had the opportunity to stay for some time at Laboratoire de Recherche en Informatique (Orsay, Université Paris-Sud), where a part of this survey was written. I would like to thank all members of Equipe Graphes from Orsay for the invitation and hospitality. This stay was partially supported by TEMPUS grant IMG-93-PL-1220.Finally, I wish to express my deep gratitude to the referee for numerous helpful comments.CONTENTSPreface............................................................................51. Introduction.................................................................5  1.1. Basic graph-theoretic terms...................................6  1.2. Some families of graphs.........................................8  1.3. Edge-disjoint placements of graphs.......................92. Embeddings of graphs................................................9  2.1. Basic result............................................................9  2.2. Self-complementary permutations........................10  2.3. Embeddings without fixed points...........................15  2.4. Graphs without small cycles..................................18  2.5. Uniquely embeddable graphs...............................233. Packing of two graphs...............................................23  3.1. Packing of two graphs of small size......................23  3.2. Packing an undense and a dense graph.............25  3.3. Products of sizes and degrees.............................26  3.4. Sum of sizes.........................................................28  3.5. Erdős-Sós Conjecture..........................................31    3.5.1. Special families of trees...................................31    3.5.2. Particular values of parameters.......................37    3.5.3. Special families of graphs................................39  3.6. Other problems related to trees and forests.........40  3.7. Some generalizations...........................................414. Packing of three graphs............................................45  4.1. Triple placement of graphs...................................45  4.2. Permutation structure...........................................50  4.3. 3-placement of a tree...........................................52  4.4. Packing three trees..............................................54  4.5. Packing three trees - general case......................58  4.6. Packing three forests...........................................585. Some special problems.............................................59  5.1. Packing a graph with its square...........................59  5.2. Careful packing of a graph...................................62  5.3. Packing of sequences of trees.............................66    5.3.1. Tree Packing Conjecture.................................66    5.3.2. Not too large trees...........................................69  5.4. Bipartite graphs....................................................70  5.5. Packing of digraphs..............................................72Bibliography...................................................................751991 Mathematics Subject Classification: 05C70, 05C35.},
author = {Woźniak Mariusz},
keywords = {graph; packing},
language = {eng},
location = {Warszawa},
publisher = {Instytut Matematyczny Polskiej Akademi Nauk},
title = {Packing of graphs},
url = {http://eudml.org/doc/271750},
year = {1997},
}

TY - BOOK
AU - Woźniak Mariusz
TI - Packing of graphs
PY - 1997
CY - Warszawa
PB - Instytut Matematyczny Polskiej Akademi Nauk
AB - PrefaceThere are two basic reference texts on packing theory: the last chapter of Bollobás's book [6] (1978) and the 4th chapter of Yap's book [85] (1986). They still remain the main references to packing problems. However, many papers related to these problems have recently been published and the reason for writing this survey is to gather in a systematic form results scattered throughout the literature.I wish I could name all who deserve my thanks. I am particularly grateful to A. P. Wojda for introducing me to graph theory, and to Z. Skupień for his interest in my research and for many stimulating conversations.During my work, I had the opportunity to stay for some time at Laboratoire de Recherche en Informatique (Orsay, Université Paris-Sud), where a part of this survey was written. I would like to thank all members of Equipe Graphes from Orsay for the invitation and hospitality. This stay was partially supported by TEMPUS grant IMG-93-PL-1220.Finally, I wish to express my deep gratitude to the referee for numerous helpful comments.CONTENTSPreface............................................................................51. Introduction.................................................................5  1.1. Basic graph-theoretic terms...................................6  1.2. Some families of graphs.........................................8  1.3. Edge-disjoint placements of graphs.......................92. Embeddings of graphs................................................9  2.1. Basic result............................................................9  2.2. Self-complementary permutations........................10  2.3. Embeddings without fixed points...........................15  2.4. Graphs without small cycles..................................18  2.5. Uniquely embeddable graphs...............................233. Packing of two graphs...............................................23  3.1. Packing of two graphs of small size......................23  3.2. Packing an undense and a dense graph.............25  3.3. Products of sizes and degrees.............................26  3.4. Sum of sizes.........................................................28  3.5. Erdős-Sós Conjecture..........................................31    3.5.1. Special families of trees...................................31    3.5.2. Particular values of parameters.......................37    3.5.3. Special families of graphs................................39  3.6. Other problems related to trees and forests.........40  3.7. Some generalizations...........................................414. Packing of three graphs............................................45  4.1. Triple placement of graphs...................................45  4.2. Permutation structure...........................................50  4.3. 3-placement of a tree...........................................52  4.4. Packing three trees..............................................54  4.5. Packing three trees - general case......................58  4.6. Packing three forests...........................................585. Some special problems.............................................59  5.1. Packing a graph with its square...........................59  5.2. Careful packing of a graph...................................62  5.3. Packing of sequences of trees.............................66    5.3.1. Tree Packing Conjecture.................................66    5.3.2. Not too large trees...........................................69  5.4. Bipartite graphs....................................................70  5.5. Packing of digraphs..............................................72Bibliography...................................................................751991 Mathematics Subject Classification: 05C70, 05C35.
LA - eng
KW - graph; packing
UR - http://eudml.org/doc/271750
ER -