Journées GALET

Coloration de graphe et applications
Soutenance de thèse

J.-S. Sereni
Projet Mascotte

Résumé

Cette thèse comporte trois parties. Dans la première partie, un problème d'allocation de fréquences, proposé par Alcatel, est modélisé en termes de coloration de graphes (la coloration impropre) : un graphe est k-improprement l-colorable s'il est possible, étant données l couleurs, d'attribuer une couleur à chacun de ses sommets de sorte que chaque sommet ait au plus k voisins de la même couleur que lui. Différentes problématiques sont ensuite étudiées : la coloration impropre (et la choisissabilité impropre) des graphes de densité bornée (englobant le cas des graphes de genre borné et de maille donnée), celle des graphes d'intersections de disques unitaires (y compris pour des instances aléatoires, et pour des ensembles de points infinis), ainsi que la coloration impropre pondérée des sous-graphes du réseau triangulaire.

La deuxième partie regroupe différents problèmes de colorations de graphes, plus ou moins reliés au problème d'allocation de fréquences, pour lesquels nous avons obtenus de nouveaux résultats. Il s'agit de la coloration 3-faciale des graphes planaires, de la choisissabilité circulaire et de diverses généralisations de l'arête-coloration des graphes cubiques, en particulier par des éléments de groupes abéliens.

Dans la troisième partie, nous nous intéressons à un problème de reroutage de requêtes, sans perte de service, dans les réseaux WDM. Dans un premier temps, un nouvel invariant des graphes est introduit afin de modéliser cette question. Comme il s'avère que ce paramètre est proche de celui, bien connu, de largeur arborescente linéaire (pathwidth), ce dernier nous a également intéressé et nous avons obtenu de nouveaux résultats concernant la relation entre la largeur arborescente linéaire d'un graphe planaire extérieur 2-connexe et celle de son dual. Plus précisément, tous les écarts possibles sont déterminés.


Frederic Havet
Last modified: Wed Jun 7 09:42:56 MEST 2006