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

Recherche transversale
(titres de publication, de périodique et noms de colloque inclus)
2016-05-26 - Colloque/Présentation - communication orale - Anglais - 42 page(s)

Devillez Gauvain , Mélot Hadrien , Hauweele Pierre , "PHOEG Helps Obtaining Extremal Graphs" in European Chapter on Combinatorial Optimization, Budapest, Hongrie, 2016

  • 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)
Texte intégral :

Abstract(s) :

(Anglais) Extremal graph theory aims to determine bounds for graph invariants as well as the graphs that attain those bounds. For example, one can study the number of non-equivalent graph colorings (defined later and called NumCol) and, given a number of nodes and edges, search to minimize it. Some invariants (including NumCol) may be hard to compute for a human and it might be difficult for one to develop intuitions about how they meld with graph structure. There is thus a need for tools to help researchers explore the intricacies of these invariants. There already are attempts to reach that goal, e.g., Graph, GrInvIn, Graffiti, AutoGraphiX, Digenes, GraPHedron. However those tools do not meet our needs to obtain extremal graphs in an exact manner and to explore graph transformations. Being able to quickly make queries on graph invariants is also an interesting feature to quickly lighten or kill ideas in a discussion, e.g., "which graphs are local minima for some transformation with respect to some invariant ?" or "on which connected graphs are two invariants equal ?". Those needs arise from our study of NumCol which is defined as follows. We say that two vertex-colorings of a graph G are equivalent if they induce the same partition of the vertex set. The number of non-equivalent proper colorings of a graph G that use exactly k colors is defined as S(G,k) and the total number of non-equivalent colorings of a graph G is defined as the sum of S(G,k) for k = 1 to n. Amongst all graphs with n vertices and m edges, we want to find the minimum possible value for NumCol. In an attempt to answer that question (and others), we are currently developing the Phoeg system, which can be viewed as a successor to GraPHedron. It uses a big database of graphs and works with the convex hull of the graphs as points in the invariants space in order to exactly obtain the extremal graphs and infer optimal bounds on the invariants. This database also allows us to make queries on those graphs as we mentioned it earlier. Phoeg goes one step further by helping in the process of designing a proof guided by successive applications of transformations from any graph to an extremal graph. This talk will present the difficulties we encounter with the NumCol problem and how the preceding ideas could be used to deal with them.

Mots-clés :
  • (Anglais) Graph theory