Quelques problèmes sur des cycles et des chaînes dans les graphes

 

Benjamin Seamone

Collège Dawson

 

Domaine : structures abstraites

Programme projet de recherche pour les enseignants de collège

Concours 2014-2015

Ce projet s'intéresse à certains problèmes reliés aux cycles et aux chaînes hamiltoniens, des concepts parmi les plus anciens et les plus étudiés en théorie des graphes. Je propose de faire de la recherche sur trois sujets particuliers, chacun basé sur une conjecture ou un domaine de recherche à la fois actuel et, dans un sens, « classique ».

D'abord, motivé par une conjecture de Chvátal de 1973, je voudrais étudier la connexion entre la robustesse d'un graphe et la présence d'un cycle hamiltonien dans ce graphe. Ensuite, je veux explorer comment généraliser les résultats de la riche littérature sur les graphes sans griffe et les cycles hamiltoniens aux graphes ayant des « nombres d'indépendance locaux » plus grands.

Finalement, motivé par une conjecture de Gyárfás de 1975, je m'intéresse au nombre chromatique des graphes dont tout sous-graphe traçable a le nombre chromatique borné. En plus de ces problèmes purement théoriques, des questions naturelles de complexité algorithmique qui en découlent (par exemple, la recherche d'un cycle particulier ou d'une coloration des sommets) seront également abordées.