Aller au menu Aller au contenu
UGA
Combinatorial Optimisation
Laboratory of Grenoble for sciences of conception, optimisation and production
Combinatorial Optimisation

Graph theory

We study a wide range of problems from Graph Theory. For instance, we are interested in coloring graphs and hypergraphs. Coloring the vertices of a graph consists in assigning them colors so that any two vertices joined by an edge have distinct colors. In general, we wish to use as few colors as possible.

Coloration du graphe de Petersen
Various problems in Operations Research, together with their applications in manufacturing process management, can be expressed as a graph coloring problem. Such problems are general difficult to solve (NP-Hard), but it is interesting to find graph classes for which they can be solved in polynomial time. Perfect graphs have this property, but the only efficient coloring algorithm that is known is impractical, and finding an algorithm that is efficient in theory and and practice is a real challenge.

Couplages parfaits

We are also interested in perfect matchings in graphs : they consist in a partition of the vertices in pairs of neighbors. The existence of a perfect matching in specific graphs (for instance, bipartite graphs) is connected to a wide range of problems in Operations Research. We also consider the problem of counting the number of perfect matchings (when we can at least certify the existence of one perfect matching) : computing this number (or an approximation) has applications in statistical physics and molecular chemistry.

Written by Louis Esperet

Date of update January 27, 2015

Communauté Université Grenoble Alpes
×
To improve the quality of this site and the service rendered to the user, we use cookies audience measurement. By continuing your visit to this site, you agree to our use of cookies for this purpose. More