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.

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.


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.