***************************** 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.