Conjectures et preuves assistées par ordinateur en théorie extrémale des graphes

Description

Le service d’Algorithmique est spécialisé dans le développement d’outils d’aide à la découverte en théorie extrémale des graphes. Les logiciels développés sont utiles tant pour générer des conjectures que pour assister à l’écriture de preuves. En particulier, les preuves par transformations de graphes sont recherchées interactivement et automatiquement. Un postdoc est possible tant au niveau du développement de ces techniques qu’au niveau théorique. En effet, diverses conjectures sous la forme de bornes sur des invariants de graphes ont été générées ou sont générées. Un sujet peut être défini en choisissant un ou plusieurs invariants de graphes à propos desquels la preuve de certaines bornes inférieures ou supérieures sont ouvertes. A titre d’exemple, nous nous intéressons au nombre de colorations non-équivalentes d’un graphe ou à l’indice de connectivité excentrique d’un graphe.