Thesis of Alice Joffard

Graph Packings

Defense date: 25/11/2020

Advisor: Hamamache Kheddouci
Coadvisor: Nicolas Bousquet


I am a third year PhD Student at the LIRIS laboratory in Lyon 1 University, under the supervision of Nicolas Bousquet and Hamamache Kheddouci. I am interested in packing problems and reconfiguration problems in graphs.

The topic of my thesis is the packing of graphs, whose goal is to find edge-disjoint copies of some graphs into another. More precisely, this problem consists in finding some conditions that allow a set of graphs H1,...,Hk to admit a packing into a graph G, a.k.a a set of injections from their vertices to the ones of G, such that the induced images of the Hi do not intersect, and are sent into the set of edges of G.I started by studying a labeled version of this problem. I also studied the simultaneous k-edge coloring of two graphs, that answers the following question: Given two graphs G and H on the same set of vertices, and of maximum degree Delta, can we color the edges of their union with Delta+2 colors, such that the restrictions to G and H are both proper edge colorings (two adjacent edges have different colors). I am also interested in reconfiguration problems in graphs, such as the reconfiguration of dominating sets, the eternal domination and the connected transformation of graphs.


Mr Liedloff MathieuMaître de conférenceUniversité d'OrléansRapporteur(e)
Mr Togni OlivierProfesseur(e)université de BourgogneRapporteur(e)
Mme Bonifati AngelaProfesseur(e)Université Lyon 1Examinateur​(trice)
Mme Brauner NadiaProfesseur(e)Université Grenoble AlpesExaminateur​(trice)
Mme Meeks KittyChercheuruniversité de GlasgowExaminateur​(trice)
Mme Nishimura NaomiProfesseur(e)Université de WaterlooExaminateur​(trice)
Mr Kheddouci HamamacheProfesseur(e)Université Lyon 1Directeur(trice) de thèse
Mr Bousquet NicolasChargé(e) de RechercheCNRSCo-directeur (trice)