DI-UMONS : Dépôt institutionnel de l’université de Mons

Recherche transversale
(titres de publication, de périodique et noms de colloque inclus)
2019-08-29 - Colloque/Article dans les actes avec comité de lecture - Anglais - 7 page(s)

Devillez Gauvain , Hauweele Pierre , Mélot Hadrien , "PHOEG Helps to Obtain Extremal Graphs" in International Conference on Operations Research, 46, 251-258, Bruxelles, Belgique, 2018

  • Codes CREF : Mathématiques (DI1100), Théorie des graphes (DI1146), Recherche opérationnelle (DI1150), Informatique mathématique (DI1160)
  • Unités de recherche UMONS : Algorithmique (S825)
  • Instituts UMONS : Institut de Recherche en Technologies de l’Information et Sciences de l’Informatique (InforTech), Institut de Recherche sur les Systèmes Complexes (Complexys)
  • Centres UMONS : Modélisation mathématique et informatique (CREMMI)

Abstract(s) :

(Anglais) Extremal Graph Theory aims to determine bounds for graph invariantsas well as the graphs that attain those bounds. We are currently devel-opping PHOEG, an ecosystem of tools designed to help researchers inExtremal Graph Theory. It uses a big database of undirected graphsand works with the convex hull of the graphs as points in the invari-ants space in order to exactly obtain the extremal graphs for some fixedparameters and infer optimal bounds on the invariants. This databasealso allows us to make queries on those graphs.For a given problem (set of invariants under consideration), PHOEG al-lows to identify conjectures about extremal graphs. Usually, this stepis not the most difficult. However, once a conjecture is highlighted,finding a general proof can be hard. To this aim, PHOEG goes onestep further by helping in the process of designing a proof guided bysuccessive applications of transformations from any graph to an ex-tremal graph. In this talk we present the ideas and techniques used inPHOEG to assist the study of Extremal Graph Theory.

Mots-clés :
  • (Anglais) graph theory
  • (Anglais) extremal graph theory
  • (Anglais) computer assisted discovery