Liens transverses ENS de Lyon

Agenda de l'ENS de Lyon

Width parameters on even-hole-free graphs

Date
mar 29 juin 2021
Horaires

14H00

Lieu(x)

Amphi B

Intervenant(s)

Soutenance de Mme SINTIARI Luh Dewi sous la Direction de thèse de M. TROTIGNON Nicolas

Langue(s) des interventions

Description générale

Les graphes sont des structures mathématiques défnies comme une paire d'ensembles (V;E), où V est un
ensemble fini (non vide) d'éléments appelés sommets (ou noeuds), et E est un ensemble ni d'éléments appelés
arêtes, dont chacun a deux sommets associés. Les graphes sont utilisés pour modéliser toutes sortes d'objets
interconnectées, comme les réseaux. Chaque objet du réseau est représenté par un sommet dans le graphe
et les arêtes représentent la relation par paire entre ces objets. Il existe de nombreux problèmes pratiques
qui peuvent être modélisés par des graphes, et les graphes ont été appliqués dans de nombreux domaines,
tels que l'informatique, les réseaux informatiques, les sciences sociales, la physique et la chimie, ou même la
linguistique.
Au cours des dernières années, l'étude des graphes s'est considérablement développée. De nombreux sujets
ont été explorés par de nombreux chercheurs du monde entier. L'un d'eux est la "théorie des stucturelle des
graphes". Ce domaine de recherche établit des résultats qui décrivent finement les adjacences dans certaines
classes de graphes. L'objectif est principalement est la conception d'algorithmes efficaces, ainsi que d'autres
applications. Dans cette thèse, nous étudions un sujet particulier sur la théorie des graphes structurels,
qui est appelée "classes héréditaires de graphes". La principale préoccupation dans ce domaine est d'étudier
comment l'exclusion de certaines configurations affecte la structure globale des graphes et quels types de
structure permettent des algorithmes efficaces pour les classes de graphes. De nombreuses classes de graphes
héréditaires sont étudiées, et dans cette thèse, nous étudions spécifiquement la classe des "graphes sans trous
pairs". Nous allons maintenant la définir formellement.

Gratuit
Mots clés
Disciplines