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.