Group for Research in Decision Analysis

House of Graphs : Quels sont les graphes intéressants ?

Hadrien Mélot Université de Mons, Belgium

Several books gather examples and counterexamples of graphs that appear frequently or play a special role in graph theory. Also conjecture-making systems in graph theory such as AutoGraphiX, Graffiti or GraPHedron allow the identification of some particular graphs that appear to be interesting (or relevant) for a given problem (e.g., as extremal graphs or as counterexamples). We start from the hypothesis that there are only a few such interesting graphs amongst the huge number of graphs. In other words, we believe that a few graphs or classes of graphs appear very frequently in numerous different problems of extremal graph theory.

We propose a framework to identify an initial set of interesting graphs by generating and solving a set of problems in an automated way, using the GraPHedron system. Also, we have designed a prototype of a web-based tool for researchers, called the House of Graphs. It can be seen as a repository of interesting graphs and complete lists for some graph classes, as well as an interface for obtaining and sharing information about them.

(Joint work with G. Brinkmann, K. Coolsaet and J. Goedgebeur)