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<br />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.<br />Différentes problématiques sont ensuite étudiées :<br />la coloration impropre (et la choisissabilité impropre) des<br />graphes de densité bornée (englobant le cas des graphes de genre borné et de maille donnée), celles des graphes d'intersection de disques unitaires (y compris<br />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.<br /><br />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, et des triplets de Steiner.<br /><br />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.<br />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<br />obtenu de nouveaux résultats concernant la relation entre la largeur arborescente lineaire d'un graphe planaire extérieur 2-connexe et celle de son dual.

Cette thèse aborde différents aspects de la conception d'un réseau de télécommunications. Un tel réseau utilise des technologies hétérogènes : liens antennes-satellites, radio, fibres optiques ou bien encore réseaux embarqués dans un satellite. Les problématiques varient en fonction de la partie du réseau considérée, du type de requêtes et de l'objectif. Le cas des requêtes de type paquets est abordé dans le cadre des réseaux en forme de grille, mais le thème principal est le routage de requêtes de type connections (unicast et multicast). Les objectifs considérés sont : la conception d'un réseau embarqué dans un satellite de télécommunication, de taille minimum et tolérant des pannes de composants; le dimensionnement des liens d'un réseau afin qu'il supporte des pannes corrélées ou qu'il offre une bonne qualité de service, ou s'il autorise des connections {\em multicast}; le dimensionnement de la taille des buffers d'un réseau d'accés radio; et l'optimisation de l'utilisation des ressources d'un réseau dynamique orienté connections. Dans tous ces cas la problématique du routage de connections est centrale. Mon approche consiste à utiliser la complémentarité de techniques algorithmique et d'optimisation combinatoire ainsi que d'outils issus de la théorie des graphes tels la pathwidth et des notions reliées -process number, jeux de captures et treewidth-, différents types de coloration -impropre et pondérée, proportionnelle, directed star colouring-, les graphes d'expansion et des techniques de partitions telle la quasi partition.