Thèse de Alice Joffard


Sujet :
Placements de graphes

Résumé :

Je suis doctorante en troisième année au laboratoire LIRIS à l'université Lyon 1 sous la supervision de Nicolas Bousquet et Hamamache Kheddouci. Je m'intéresse aux problèmes de placements et de reconfigurations dans les graphes.

Le sujet de ma thèse est le placement de graphes, dont le but est de trouver des copies arêtes-disjointes de certains graphes dans un autre. Plus précisement, ce problème consiste à trouver des conditions pour qu'un ensemble de graphes H1,...,Hk admette un placement dans un graphe G, c'est à dire un ensemble d'injections de leurs sommets vers ceux de G, tel que les images induites des arrêtes des Hi ne s'intersectent pas, et soient envoyées dans l'ensemble des arêtes de G. J'ai étudié dans un premier temps une version étiquetée de ce problème. Je me suis également penchée sur la k-coloration d'arêtes simultanée de deux graphes, qui répond à la question suivante: étant donnés deux graphes G et H sur le même ensemble de sommets, et de degrés maximums Delta, peut-on colorer les arêtes de leur union avec Delta + 2 couleurs, de sorte que les restrictions à G et H soient toutes les deux des colorations d'aretes propres (deux aretes adjacentes ont des couleurs différentes)? Je m'intéresse également aux problèmes de reconfiguration dans les graphes, notamment à la reconfiguration d'ensembles dominants, à la domination éternelle et aux transformations connexes de graphes.


Encadrant : Hamamache Kheddouci
Co-encadrant : Nicolas Bousquet