Identifiant pérenne de la notice : 226719456
Notice de type
Notice de regroupement
Note publique d'information : 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
: un graphe est K-improprement L-colorable s’il est possible, étant donné 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. La coloration impropre (et la choisissabilité
impropre) des graphes de densité bornée (englobant les graphes de genre et de maille
donnés), celle des graphes d’intersection de disques unitaires (y compris pour des
instances aléatoires et des ensembles de points infinis) et la coloration impropre
pondérée des sous-graphes du réseau triangulaire. La deuxième partie regroupe notre
étude de différents problèmes de colorations de graphes : la coloration 3-faciale
des graphes planaires, la choisissabilité circulaires et diverses généralisations
de l’arrête-coloration des graphes cubiques, en particulier par des éléments de groupes
abéliens et des triplets de Steiner. Dans la troisième partie, nous nous intéressons
au reroutage de requêtes sans perte de service dans les réseaux WOM. Uun nouvel invariant
des graphes est défini afin de modéliser cette question. Comme il s’avère que ce paramètre
est proche de celui de largeur arborescente linéaire (pathwidth), ce dernier nous
a intéressé aussi 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.
paprika.idref.fr
data.idref.fr
Documentation
