Dans cette thèse, nous étudions plusieurs problèmes de théorie des graphes concernant la coloration et la convexité des graphes. La plupart des résultats gurant ici sont liés à la complexité de calcul de ces problèmes pour certaines classes de graphes. Dans la première, et principale, partie de cette thèse, nous traitons de coloration des graphes qui est l'un des domaines les plus étudiés de théorie des graphes. Nous considérons d'abord trois problèmes de coloration appelés coloration gloutone, coloration pondérée et coloration pondérée impropre. Ensuite, nous traitons un probl ème de décision, appelé bon étiquetage de arêtes, dont la dé nition a été motivée par le problème d'affectation de longueurs d'onde dans les réseaux optiques. La deuxième partie de cette thèse est consacrée à un paramètre d'optimisation des graphes appelé le nombre enveloppe (géodésique). La dé nition de ce paramètre est motivée par une extension aux graphes des notions d'ensembles et d'enveloppes convexes dans l'espace Euclidien. En n, nous présentons dans l'annexe d'autres travaux développées au cours de cette thèse, l'un sur les hypergraphes orientés Eulériens et Hamiltoniens et l'autre concernant les systèmes de stockage distribués.
| Identifer | oai:union.ndltd.org:CCSD/oai:tel.archives-ouvertes.fr:tel-00732919 |
| Date | 13 September 2012 |
| Creators | Araujo, Julio |
| Publisher | Université de Nice Sophia-Antipolis |
| Source Sets | CCSD theses-EN-ligne, France |
| Language | English |
| Detected Language | French |
| Type | PhD thesis |
Page generated in 0.0019 seconds