Abstract : Un k-flot non-nul dans un graphe est une orientation des arêtes et une assignation d'entiers entre 1 et k à chaque arête qui vérifie la loi de conservation du flot autour de chaque sommet. J'évoquerai plusieurs conjectures et problèmes ouverts classiques sur les flots non-nuls dans les graphes (en particulier les conjectures des 3-flots et 5-flots de Tutte), ainsi que des avancées récentes sur ces questions. Un couplage parfait dans un graphe est un ensemble d'arêtes qui couvre chaque sommet exactement une fois. Je mentionnerai également plusieurs problèmes importants autour des couplages parfaits dans les graphes cubiques (il existe des liens intéressants, plus ou moins compris, entre flots non-nuls et couverture par des couplages parfaits).

Abstract : I would like to share with you some open combinatorial problems related to Linear Programming (LP) with their context and some recent news. Some of them are useful, some others "only" possibly interesting. Three examples: Is it possible to find a path between two given vertices of a graph, which is 50% longer than the result of a natural LP relaxation ? This looks more hopeful than the famous 4/3 for s=t. Is there a solution to the bin packing problem which uses one more bin than the LP relaxation ? The same question exists for the chromatic index if viewed as a packing of matchings. Are these OR problems ? Or CO ? Discrete Mathematics ? Networks ? Graph Theory ? No prerequisites will be supposed, LP will also be present only through a simple proposition that will be explained.

Abstract : The 1-2-3 Conjecture, posed in 2004 by Karonski, Luczak and Thomason, asserts that, for every connected graph different from K_2, we can label its edges with labels 1,2,3 so that no two adjacent vertices receive the same sum of incident labels. Despite many efforts, this conjecture is still widely open to date; yet, many interesting works and approaches towards the understanding of both its main and side aspects have been initiated. This talk will be meant as a high-level introduction to the field, covering both the original conjecture and variants of it (including, notably, optimisation variants). For each of those problems, we will survey both most of all the results we know, as well as some of the numerous main and side questions that remain open.

Abstract : En 1982, Sands, Sauer et Woodrow montrent que tout graphe orienté dont les arcs sont bi-colorés admet un ensemble indépendant S (aucune paire de sommets de S ne peut être reliée par un chemin monochromatic) où chaque sommet peut être atteint par un chemin monochromatic partant de S. Ce résultat permet, entre autres, de donner une autre preuve du théorème de Gale-Shapley sur les mariages stables. Si les arcs du graphes orientés sont coloriés avec au moins 3 couleurs, ce résultat n'est plus vrai (il suffit de considérer un triangle orienté tri-colorié). Cependant, Sands Sauer et Woodrow conjecturent alors de l'existence d'une fonction f, telle que pour tout graphe orienté dont les arcs sont k-coloriés, il existe un ensemble de f(k) indépendants tels que chaque sommet peut être atteint par un chemin monochromatic partant de l'un de ces indépendants. L'existence de la fonction f reste ouverte dès k = 3. L'exposé présentera aussi la preuve de la conjecture de Sands Sauer et woodrow dans le cas des tournois qui a été prouvée récemment par Bousquet, Lochet et Thomassé.