Titre : Une preuve courte d'un résultat de choisissabilité dans les

graphes planaires

Exposant : Nathann Cohen

Résumé : L'index chromatique d'un graphe -- noté \chi'(G) -- est

égal au nombre minimum de couleurs nécessaires pour colorer les arêtes

d'un graphe de telle facon que deux arêtes incidentes aient des

couleurs différentes (on dit alors que la coloration est propre).

L'arête-choisissabilité est une forme contrainte de coloration

d'arêtes : on commence par associer a chaque arête du graphe une liste

de k entiers arbitraires, puis on tente de colorer proprement les

arêtes en n'utilisant pour celles-ci que les couleurs disponibles dans

leurs listes associées. Le plus petit $k$ tel qu'il existe pour toute

assignation de liste une telle coloration propre est noté

\chi'_c(G). La list-coloring conjecture suppose depuis longtemps

l'égalité \chi'(G) = \chi'_c(G) mais nous en sommes encore loin. Cet

exposé consiste en une preuve courte d'un résultat de Borodin qui

affirme que les graphes planaires de degré maximum Delta \geq 9

vérifient chi'_c(G) \leq \Delta+1. La coloration s'obtient à l'aide

d'un algorithme simple consistant en deux opérations et découle de la

preuve du résultat.