Colorations de graphes et applications

摘要: Cette these comporte trois parties. Dans la premiere partie, un probleme d'allocation de frequences, propose par Alcatel, est modelise en termes coloration graphes : graphe k-improprement l-colorable s'il possible, etant donnees l couleurs, d'attribuer une couleur a chacun ses sommets sorte que chaque sommet ait au plus k voisins meme lui. Differentes problematiques sont ensuite etudiees impropre (et choisissabilite impropre) des densite bornee (englobant le cas genre borne et maille donnee), celles d'intersection disques unitaires (y compris pour instances aleatoires, ensembles points infinis), ainsi ponderee sous-graphes du reseau triangulaire. La deuxieme partie regroupe differents problemes colorations graphes, ou moins relies lesquels nous avons obtenus nouveaux resultats. Il s'agit 3-faciale planaires, circulaire diverses generalisations l'arete-coloration cubiques, particulier elements groupes abeliens, triplets Steiner. troisieme interessons reroutage requetes, sans perte service, dans les reseaux WDM. premier temps, nouvel invariant introduit afin modeliser cette question. Comme il s'avere ce parametre proche celui, bien connu, largeur arborescente lineaire (pathwidth), dernier egalement interesse obtenu resultats concernant relation entre d'un planaire exterieur 2-connexe celle son dual.