titre du sujet: Colorations et
Flots antisymétriques
- encadrant: André
Raspaud
- laboratoire et équipe
de recherche: LaBRI : équipe Graphes et
Applications
- description détaillée
:
Les problèmes de colorations et de flot non-nuls sont au
coeur de la théorie des graphes. Les
notions de colorations
orientées développées récemment ont
donné lieu à de nombreuses
recherches et les extensions aux
graphes mixtes donnent de nouvelles
ouvertures. Les flots antisymétriques
sont liés par dualité à
la notion de colorations fortes
dans le cas planaire. L'existence de flot
non-nul est en un certain sens une
notion non orientée alors que
l'existence de flot antisymétrique
dépend de l'orientation.
La problèmatique des flots antisymétriques n'est pas encore
bien
unifée. Ce qui rend l'approche plus
délicate.
Le but de cette thèse est de bien mettre en place ces
notions ainsi que leurs relations
afin d'avoir une
théorie cohérente. Des nombreux
problèmes ne sont
pas résolus en voici quelques uns:
- Dans le cas planaire peut-on améliorer la borne
actuellement connue
pour l'existence d'un flot antisymétrique.
- Pour certaines familles de graphes peut-on prouver aisément
l'existence de flot antisymétrique.
- Dans la cas particulier des graphes eulériens, est -il
possible de dégager des bornes
selon le type d'orientation.
- Si la connexité (arête) est grande on peut espérer avoir
des
bornes intéressantes.
- La notion d'homomorphisme est centrale pour les problèmes
de
colorations. Dans le cas des flots,
certaines applications entre les
espaces de cycles sont définies,
peut-on les particulariser pour les
flots antisymétriques.
- La notion duale de cette notion de flot est la coloration forte,
cette dernière peut être étendue
aux graphes mixtes, il est naturel
d'étendre de même la
notion de flot antisymétrique, ce
qui permettrait de d'avoir des
résultats plus synthétiques.
Dans la majorité des cas il s'agit de problèmes
d'optimisation
combinatoire où la dualite existant
entres les notions intoduites
peut être d'une grande utilité. Nous pensons aussi privilégier
l'approche algorithmique de cette étude.