Séance Séminaire

Soutenances de thèses

Etude des classes de graphes et de matroïdes closes par mineur : densité de triangles, coloration, rigidité et orientations

Jury: Jorge RAMIREZ ALFONSIN, UM2, Co-directeur de thèse Daniel GONCALVES, UM2, Co-directeur de thèse Andras SEBO, UJF, Rapporteur Patrice OSSONA DE MENDEZ, EHESS, Rapporteur Victor CHEPOI, Université Aix Marseille Résumé : La théorie des mineurs de graphes est apparue dans la première partie du XXème siècle avec la caractérisation des graphes planaires par Kuratowski et Wagner. L'étude des classes de graphes closes par mineurs intervient dans de nombreux domaines en théorie des graphes (graphes plongés dans les surfaces, coloration, théorie extrémale des graphes, théorie de la rigidité, ...). Dans la première partie de cette thèse, nous prouverons l'existence de mineurs de graphes complets dans des graphes dont toutes les arêtes appartiennent à un certain nombre de triangles. Cette propriété trouve des applications dans la théorie de la rigidité des graphes ainsi qu'à la coloration de certaines classes de graphes closes par mineurs. Une seconde partie est consacrée à la généralisation de cette propriété des graphes vers les matroïdes. Les matroïdes sont des objets combinatoires introduits en 1935 par Whitney qui ont pour but d'axiomatiser le concept d'indépendance linéaire. En particulier, les notions de triangle et de mineur de graphe peuvent se généraliser à ces objets. Nous étudierons donc les matroïdes dont tous les éléments appartiennent à un certain nombre de triangles et montrerons que l'on peut trouver certains mineurs particuliers dans ces matroïdes. Enfin, une dernière partie de cette thèse sera consacrée à l'étude de certaines orientations des graphes plongés dans les surfaces.