*****************************

Directeurs de thèse : A. Raspaud, M. Montassier
Equipe : Combinatoire et Algorithmes
Couriel : raspaud@labri.fr, montassi@labri.fr


Nature du sujet :

Renforcement d'une thématique scientifiquement reconnue : Les
problèmes de flots dans les graphes sont au cœur de la théorie des
graphes. La conjecture célèbre de Tutte est toujours d'actualité et
est le sujet de nombreuses recherches.


Développement d'une thématique émergente :
 La notion de flot circulaire a été introduite ces dernières années et est une importante direction de recherche.

Collaboration internationale:
Cette recherche s'intègre dans une collaboration (accord CNRS/NSC) avec l'Université Sun-Yat Sen de Taiwan.

Description synthétique du sujet (maximum 10 lignes):

  La notion de flots est au cœur de la théorie des graphes et a donné
  lieu à de nombreuses études et conjectures : la conjecture des cinq
  flots de Tutte, le théorème des six flots de Seymour... Plus
  récemment, la notion de flots circulaires a été introduite par Luis
  Goddyn et Xuding Zhu, elle permet une nouvelle approche pour tenter
  de prouver des conjectures plus anciennes comme celle de Jaeger.

Cette thèse a pour but le développement de nouvelles approches
algébriques, algorithmiques et probabilistes afin de progresser dans
la résolution d'une conjecture de Jaeger et dans la résolution de la
conjecture du cinq flot de Tutte.

Description détaillée du sujet:

Dans le cas des graphes planaires, la notion de flot circulaire est la
 notion duale de la notion de coloration circulaire. La coloration
 circulaire a été très étudiée ces dernières années. L'étude des flots
 circulaires est importante, en effet de nombreuses conjectures au
 coeur de la théorie des graphes peuvent être approchée à l'aide de
 cette notion.  En particulier la célèbre conjecture de Jaeger qui en
 termes de flots circulaires s'écrit: Tout graphe 4k-arête connexe a
 un nombre de flot circulaire au plus 2+ 1/k.  Cette conjecture a
 donné lieu à des travaux intéressants lorsque celle-ci est restreinte
 à la famille des graphes planaires. Dans ce cas il est prouvé que
 tout graphe planaire de maille impaire plus grande ou égale à 8k-3 a
 un nombre chromatique circulaire au plus 2+ 1/k.  Une version plus
 faible de la conjecture de Jaeger est la suivante: Si
 l'arête-connectivité d'un graphe est suffisamment grande alors son
 nombre de flot circulaire est proche de 2.  Par des méthodes
 probabilistes on sait que cette version faible de la conjecture de
 Jaeger est vraie pour presque tous les graphes.  Il serait
 intéressant de prouver cette version faible de la conjecture pour
 certaines familles de graphes et d'aborder d'autres conjectures
 concernant les flots non-nuls dans les graphes.  Dans le cas de
 l'existence du 6-flot non nul il existe des algorithmes pour trouver
 le 6-flot non nul. Dans le même ordre d'idée le coté algorithmique de
 l'étude proposée doit être développée. Les résultats existentiels
 obtenus doivent nous permettent de construire des algorithmes
 efficaces de colorations circulaires ou de calcul de flots
 circulaires.

Objectifs Progresser dans la résolution de la conjecture de Jaeger et
dans la résolution de la conjecture des cinq flots de Tutte.

Méthodologie
Développement d'outils algébriques, algorithmiques et probabilistes.

  Bibliographie [1] F. Jaeger. Nowhere zero-flow Problems, Selected
topics in Graph Theory 3, Academic Press, London (1988) p.71-95.

[2] W.T. Tutte. A contribution to the theory of chromatic
polynomials. Canad. J. Math. 6 (1954) p.80-91.

[3] X. Zhu. Planar Graphs with circular chromatic numbers between 3
and 4. J. Combin. Th. (B), 76 (1999) p.170-200.