Personal tools
Laboratoire d'InfoRmatique en Image et Systèmes d'information

Skip to content. | Skip to navigation

Laboratoire d'InfoRmatique en Image et Systèmes d'information
UMR 5205 CNRS / INSA Lyon / Université Claude Bernard Lyon 1 / Université Lumière Lyon 2 / École Centrale de Lyon
You are here: Home > membres

Alice Joffard


PhD student

Team Graphes, AlgOrithmes et AppLications
Institution Claude Bernard University of Lyon 1
Location Nautibus (Université Lyon1)
E-mail alice.joffard at
Contact details Publications Thesis
Subject The goal of this thesis is to study different versions of the problem of graph packing, that consists in finding edge disjoint copies of given graphs into a target graph.
Abstract The graph packing problem has applications in many fields : chemistry, social networks, bioinformatics, etc. In practice, the problem consists in finding a structure or a substructure in another one under certain constraints. The general case of the packing of any graph into another is NP-complete. Among the first results on the graph packing problem, or on the existence of subgraphs problem, we mention Dirac's result in 1952 that shows the existence of a hamiltonian cycle in a graph, depending on its minimal degree. Erdös and Gallai, in 1959, showed the existence of a chain of length k in a graph of order n if its size is strictly superior to n(k-1)/2. In 1978, Spencer and Sauer showed that two graphs of order n and size n-2 are placeable in Kn. Many results and conjectures are well-known in the field. We mention in particular two conjectures that are interesting for this thesis, such as the conjecture of Bollobás and Eldridge in 1978 that states that k graphs of order n and size at most n-k are placeable in the complete graph of order n. The second conjecture, known as the Tree Packing Conjecture (TPC) of Gyárfás and Lehel in 1976 states that it is always possible to place a sequence of trees T1, T2, ..., Tn into Kn, with Ti a tree of order i.
Very recently, Tahraoui and al. studied a labeld version of the graph packing problem. Results have been obtained for trees and cyles in particular.
The goal of this thesis is to study the case of graphs that are:
1. Unoriented and unlabeled, the conjectures of Bollobás and Eldridge, and Gyarfas and Lehel previously mentioned. Concerning the first conjecture, only the cases k=2 and k=3 are resolved. Concerning the second conjecture, a known partial result is the one of Bollobás in 1982 in which he shows that the conjecture is true in the case where the number of trees to pack is at most n√2/2. More recently, several results about particular tree sequences were found. The conjecture is still open.
2. Labeled, generalizations and characterizations of families of labeled graphs placeable in the complete graph and other graphs such as powers of graphs, hypercubes, etc. The only known results are the ones limited to particular classes of graphs.
3. Oriented, where few results are known. In particular, we will study the packing of oriented graphs into the complete symmetric graph. Studies similar to the ones led on unoriented graphs will be led on oriented graphs.
Advisor Hamamache Kheddouci

Last update : 2018-02-02 11:47:52