Telephone : (+33) 4 76 57 47 03Fax : (+33) 4 76 57 46 02
Department of Discrete Mathematics,
Leibniz Laboratory,
IMAG Institute, Grenoble, France
Telephone : (+33) 4 76 57 47 03
Fax : (+33) 4 76 57 46 02
Education - Activities - Publications - Conferences -
My picture (77 K)
- Born on 28 July 1954 in Zürich (Switzerland),
- Junior Researcher (Chargé de Recherche) at the CNRS,
- Leader of the Graph Theory team in the laboratory.
- Thesis, "Sur les colorations des arêtes des graphes cubiques" (on edge colorings in cubic graphs), University of Grenoble, May 1981 (under the direction of François Jaeger).
- Thesis (Thèse d'Etat), "Sur quelques problèmes théoriques et appliqués de la théorie des graphes" (on some theoretical and applied problems in graph theory), University of Grenoble, December 1988 (under the direction of Jean Fonlupt).
My work has had several orientations thanks to the different positions I had and the subjects which interested me.
For my "first thesis" under the direction of François Jaeger I studied cubic graphs and their edge-colourings. These notions were initially studied because of their relationship with the four-colour conjecture, of which a formulation is: every cubic bridgeless planar graph has chromatic index 3. I obtained mainly two results: 1.) I disproved a theorem of Szekeres characterizing cubic graphs of chromatic index 3. There are several counterexamples to this theorem and particularly an infinite family. 2.) I defined c-minimal snarks; they form a class of cubic graphs of chromatic index 4 from which we can obtain every cubic graph of chromatic index 4 using a set of constructions. By defining new constructions, I restricted the class of snarks defined by R. Isaacs, which have the same property. Furthermore the results obtained for my thesis enabled me to prove that there are only two snarks of order 18.
I was for one and a half year a participant of a European project for the computer-assisted design of VLSI circuits. The CASCADE language that we developed enables us to describe a circuit, and this description is treated to make the simulation of the circuit easier. I have developed several practical and theoretical algorithms to make this simulation faster.
I have also worked with some physicist in statistical physics. We established the complexity of combinatorial problems associated with several physical models and designed some polynomial algorithms including a post-optimality procedure.
After my thesis I worked at the Ecole Polytechnique Federale de Lausanne as an assistant of Professor Dominique de Werra. There my research oriented towards the field of perfect graphs. For these graphs the four important problems of the graph theory which are NP-complete in general are polynomial [Grotschel, Lovasz and Schrijver]. Another interesting question about perfect graphs is Berge's famous Strong Perfect Graph Conjecture. I obtained several results concerning new classes of perfect graphs, new properties of minimal imperfect graphs, algorithmic properties, and other related questions.
Perfect graphs are now the main subject of my research. There are many interesting and important unsolved questions. But I am also interested in any problems related to Graph Theory especially when they have practical applications.
Back to the list of members of the Graph Theory
team of the Leibniz Laboratory,or to the home page of the team.
