Abstract FR:

Le coloriage de graphe est un problème combinatoire NP-difficile de base, apparaissant dès que l'on doit regrouper ensemble des objets (les sommets du graphe) dont on connaît des paires devant être séparées (les arêtes). C'est donc un problème central en allocation de fréquences, où l'on doit affecter des fréquences à des liaisons radio pour éviter les interférences. Parmi les nombreuses approches pour colorier un graphe avec le moins de couleurs possibles, nous avons choisi de relâcher les contraintes d'une formulation du problème ; on obtient ainsi un problème éventuellement plus facile à résoudre, fournissant une borne et une solution relâchée qu'il faudra arrondir. Nous nous sommes concentrés sur les formulations utilisant la programmation semi-définie. La meilleur borne polynomiale (semi-définie) du nombre minimum de couleurs est la borne dite de Lovasz. Nous en avons utilisé la formulation la plus adaptée au coloriage pour approcher l'ensemble des colorations d'un graphe, ce qui nous a permis d'enir de bonnes solutions à un problème de coloriage avec une fonction de coût originale, dérivé de l'allocation de fréquences. Mais en utilisant une nouvelle formulation de coloriage, dont le nombre de Lovasz est une relaxation continue simple, nous avons pu renforcer cette borne. Cependant, l'origine de la formulation du nombre de Lovasz restait mal connue; nous avons présenté un schéma de quadratisation "simple" permettant d'obtenir cette formulation à partir d'une modélisation linéaire de coloriage, ainsi qu'une quadratisation "systématique" de cette modélisation linéaire, fournissant une nouvelle formulation du nombre de Lovasz. Ce second schéma, quoique peu pratique, permet d'obtenir des bornes sur une extention de coloriage à une famille de problèmes d'allocation de fréquences.