"Techniques de preuve par dénombrement en théorie des graphes"

Il y a vingt ans, Carsten Thomassen a fait la conjecture que tout circuit de longueur maximum dans un graphe 3-connexe admet une corde (une arête reliant deux sommets non consécutifs du circuit). Tout récemment, il a pu résoudre un cas spécial de cette conjecture, le cas des graphes 3-réguliers. Sa jolie démonstration repose sur une technique de preuve inventée par Andrew Thomason, la technique de sucettes  (lollipops), dont plusieurs applications intéressantes ont été déjà trouvées. La preuve de Thomassen fait appel également à un théorème de Fleischner et Stiebitz dont la démonstration dépend de la théorie du polynôme du graphe  développée par Alon et Tarsi. La technique de Thomason, ainsi que celle d'Alon et Tarsi, se sert d'un raisonnement par dénombrement. Ceci est le sujet de notre exposé.

E-mail: jabondy@ccr.jussieu.fr