Trois résultats en théorie des graphes

Cette thèse réunit en trois articles mon intérêt éclectique pour la théorie des graphes.
\n
\nLe premier problème étudié est la conjecture de Erdos-Faber-Lovász:
\nLa réunion de k graphes complets distincts, ayant chacun k sommets, qui ont deux-à-deux au plus un sommet en commun peut être proprement coloriée en k couleurs.
\nCette conjecture se caractérise par le peu de résultats publiés. Nous prouvons qu’une nouvelle classe de graphes, construite de manière inductive, satisfait la conjecture. Le résultat consistera à présenter une classe qui ne présente pas les limitations courantes d’uniformité ou de régularité.
\n
\nLe deuxième problème considère une conjecture concernant la couverture des arêtes d’un graphe: 
\nSi G est un graphe simple avec alpha(G) = 2, alors le nombre minimum de cliques nécessaires pour couvrir l’ensemble des arêtes de G (noté ecc(G)) est au plus n, le nombre de sommets de G.
\nLa meilleure borne connue satisfaite par ecc(G) pour tous les graphes avec nombre d’indépendance de deux est le minimum de n + delta(G) et 2n − omega(racine (n log n)), où delta(G) est le plus petit nombre de voisins d’un sommet de G. Notre objectif a été d’obtenir la borne ecc(G) <= 3/2 n pour une classe de graphes la plus large possible. Un autre résultat associé à ce problème apporte la preuve de la conjecture pour une classe particulière de graphes:
\nSoit G un graphe simple avec alpha(G) = 2. Si G a une arête dominante uv telle que G \\ {u,v} est de diamètre 3, alors ecc(G) <= n.
\n
\nLe troisième problème étudie le jeu de policier et voleur sur un graphe. Presque toutes les études concernent les graphes statiques, et nous souhaitons explorer ce jeu sur les graphes dynamiques, dont les ensembles d’arêtes changent au cours du temps. Nowakowski et Winkler caractérisent les graphes statiques pour lesquels un unique policier peut toujours attraper
\nle voleur, appellés cop-win, à l’aide d’une relation <= définie sur les sommets de ce graphe:
\nUn graphe G est cop-win si et seulement si la relation <= définie sur ses sommets est triviale.
\nNous adaptons ce théorème aux graphes dynamiques. Notre démarche nous mène à une relation nous permettant de présenter une caractérisation des graphes dynamiques cop-win. Nous donnons ensuite des résultats plus spécifiques aux graphes périodiques. Nous indiquons aussi comment généraliser nos résultats pour k policiers et l voleurs en réduisant ce cas à celui d’un policier unique et un voleur unique. Un algorithme pour décider si, sur un graphe périodique donné, k policiers peuvent capturer l voleurs découle de notre caractérisation.

Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.