Quelques variations très chromatiques seront illustrées avec des motivations esthétiques et même pratiques ; cherchant à atteindre des sommets et suivant d'innombrables arêtes, il sera procédé à quelques extensions d'ordre musculaire où il s'agira de manier des poids, ce qui soulèvera des montagnes de problèmes nouveaux. Mais on n'oubliera pas pour autant le cas usuel où l'on a tous les poids des haltères égaux.

Les polynômes chromatiques des graphes ont été introduits en 1912 par G.D. Birkhoff pour étudier le problème des quatre couleurs. Etant donné un graphe G, le polynôme chromatique P(G, x) associé à G est tel que, pour tout entier x, P(G, x) indique le nombre de colorations différentes de G à l'aide de x couleurs. Plus précisément, les polynômes chromatiques sont définis récursivement à partir de la supression ou de la contraction d'une arête par : P(G, x) = P(G - a, x) - P(G/a, x), où a est une arête quelconque de G, où G - a désigne le graphe obtenu en supprimant a de G, et où G/a désigne le graphe obtenu en contractant a dans G. On s'intéresse ici à la valeur des racines des polynômes chromatiques des graphes quelconques ou au contraire de graphes particuliers comme les graphes planaires, les graphes hamiltoniens ou les graphes de degré majoré...

L'objet de la tomographie discrete est la reconstruction d'un objet discret a partir de ses projections. Nous allons presenter
quelques problemes de base de cette discipline comme la reconstruction d'un tableau colore ou la reconstruction du pavage d'un rectangle par des dominos. Nous formulerons aussi ces problemes en termes de graphes, d'ordonnancements et presenterons quelques applications concernant la construction de planning de personnel.

On assiste des dernières années à une densification du besoin : augmentation de la demande (de plus en plus d'utilisateurs et de nouveaux services) dans une ressource spectrale qui reste physiquement inextensible. Ce constat conduit à chercher à optimiser toujours plus la gestion des fréquences. Depuis le projet CALMA (Combinatorial Algorithms for military applications), la modélisation des contraintes a évolué et continue d'évoluer pour approcher au mieux la réalité physique. L'objectif de cette présentation consiste à illustrer certaines de ces évolutions sur le cas assez générique de l'allocation des fréquences pour les faisceaux hertziens.

En 1961 Claude Berge a introduit la notion de graphes parfaits et a énoncé une célèbre conjecture connue sous le nom de "Conjecture Forte des Graphes Parfaits". Cette conjecture vient juste d'être démontrée par Paul Seymour, Robin Thomas et deux autres chercheurs. L'importance des graphes parfaits réside dans le fait que leur étude s'inscrit dans de nombreux domaines tels que les
structures combinatoires générales, l'optimisation discrète, les polyèdres entiers, la programmation linéaire, la complexité des algorithmes, l'algorithmique combinatoire. Nous présentons dans cet exposé ces diverses approches en mettant l'accent sur les opérations de décomposition des graphes parfaits qui ont permis d'établir la preuve récente de la validité de la Conjecture Forte des Graphes Parfaits.