Groupe d’études et de recherche en analyse des décisions

G-2016-90

Finding conjectures in graph theory with AutoGraphiX

, , , et

Les heuristiques basées sur la théorie des graphes sont largement utilisées dans plusieurs domaines pour résoudre approximativement des problèmes d'optimisation de grandes tailles. Elles sont aussi ulilisées pour faire progresser la théorie des graphes per se, i.e. réfuter, trouver, corroborer, prouver ou donner des idées de preuve des conjectures sur des invariants graphiques, i.e., des paramètres numériques indépendants de la numérotation des sommets ou des arêtes. Dans cet article, nous présentons et discutons le système AutoGraphiX qui trouve automatiquement ou, dans certains cas, interactivement des conjectures en théorie des graphes. Nous considérons en particulier des conjectures sur des paires d'invariants pris d'un ensemble de vingt.

, 22 pages