Thesis of Alice Joffard


Subject:
Graph Packings

Summary:

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.

 


Advisor: Hamamache Kheddouci
Coadvisor: Nicolas Bousquet

Defense date: wednesday, november 25, 2020

Jury:
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)