Etude des classes de graphes et de matroïdes closes par mineur : densité de triangles, coloration, rigidité et orientations - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Thèse Année : 2014

A study of minor-closed classes of graphs and matroids : triangle density, coloring , rigidity and orientations

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

Résumé

The theory of graph minors appeared in the first part of the twentieth century with the characterization of planar graphs by Kuratowski and Wagner. The study of classes of graphs closed under minors has applications to many areas of graph theory (graphs embedded in surfaces, coloring, extremal graph theory, theory of rigidity, ...). The first part of this thesis is devoted to prove the existence of minors of complete graphs in graphs where each edge belongs to a certain number of triangles. This property has applications to the theory of rigidity and to the coloration of some minor-closed classes. A second part is devoted to the generalization this property from graphs to matroids. Matroids are combinatorial objects introduced in 1935 by Whitney to axiomatize the concept of linear independence. In particular, the notions of triangle and minor can be generalized to these objects. We will study matroids in which every element belongs to a certain number of triangles and show that we can find some particular minors in these matroids. Finally, the last part of this thesis is devoted to the study of certain orientations of graphs embedded in surfaces.
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.
Fichier principal
Vignette du fichier
ALBAR_2014_archivage.pdf (2.2 Mo) Télécharger le fichier
Origine : Version validée par le jury (STAR)
Loading...

Dates et versions

tel-02588079 , version 1 (15-05-2020)

Identifiants

  • HAL Id : tel-02588079 , version 1

Citer

Boris Albar. Etude des classes de graphes et de matroïdes closes par mineur : densité de triangles, coloration, rigidité et orientations. Mathématique discrète [cs.DM]. Université Montpellier II - Sciences et Techniques du Languedoc, 2014. Français. ⟨NNT : 2014MON20209⟩. ⟨tel-02588079⟩
175 Consultations
213 Téléchargements

Partager

Gmail Facebook X LinkedIn More