Fifth ANR Digraph meeting

Sète May 30 – June 2, 2023.

Pierre Aboulker, Guillaume Aubian, Joergen Bang-Jensen,
Stéphane Bessy, Romain Biourneuf, Pierre Charbit, Julien Duron, Colin Geniet, Emeric Gioan, Daniel Gonçalves, Ararat Harutyunyan, Frédéric Havet, Florian Hoersch, Hugo Jacob, Kolja Knauer, William Lochet, Yann Marin, Lucas Picasarri-Arrieta, Gil Puigi-Surroca, Clément Rambaud, Amadeus Reinald, Stéphan Thomassé, Nicolas Trotignon, Petru Valicov, Rémi Watrigant, Raul Wayne, Anders Yeo

Programme :

Mardi 30 Mai
9h30-10h30 Joergen Bang-Jensen : Open problem in digraphs. Slides

10h45-12h00 Open Problems Session 1.
14h00-15h00 Open Problems Session 2.  Open Problems of the 2 sessions

15h15-15h50 Raul Lopes :  New Menger-like dualities in digraphs and applications to half-integral linkages.

Mercredi 31 Mai
9h30-10h30 Anders Yeo : Directed max-cut and some generalizations. Slides
10h45-11h25 Guillaume Aubian : Maximum local arc-connectivity and dichromatic number. Slides
11h30-12h15 Julien Duron : On the minimum number of inversions to make a digraph k-(arc-)strong. Slides


14h30-15h00 Yann Marin : Oriented matroid convexity in directed graphs.

Jeudi 1er Juin

9h45-10h30 Colin Geniet : A tamed family of triangle-free graphs with unbounded chromatic number
10h45-11h15 Lucas Picasarri-Arrieta : On the minimum number of arcs in 4-dicritical oriented graphs. Slides
11h20-12h00: Gil Puigi-Surroca : Dichromatic number/list number of some families of digraphs. Slides

Vendredi 2 Juin

10h00 : Solved  problems.

Fourth ANR Digraph meeting

Lyon January 25 – 27, 2023.

Pierre Aboulker, Guillaume Aubian,
Stéphane Bessy, Julien Duron, Colin Geniet, Emeric Gioan, Daniel Gonçalves, Frédéric Havet, Yann Marin, Nicolas Nisse, Lucas Picasarri-Arrieta, Pegah Pournajafi, Clément Rambaud, Amadeus Reinald, Stéphna Thomassé, Nicolas Trotignon, Rémi Watrigant

Programme :
A partir de 9:00 : accueil café, discussion libre
10:00 – 11:30 : séance de problèmes ouverts,  présence de tous attendu 
11:30 : déjeuner
13:30 – 14:30 Ramsey Problem for the dichromatic number
Par Pierre Aboulker
15:00 – 18:00 Suite des problèmes ouverts, travail en groupe
10:00 Progrès sur les inversions 
Par Clément Rambaud
11:30 Déjeuner
13:30 : Problèmes ouverts puis travail en groupe
10:00 Reconfigurations de dicolorations.
Par Lucas Picasarri-Arrieta
11:30 Déjeuner
13:30: Travail en groupe

Third ANR Digraph meeting

Les Plantiers June 27 – July 3, 2022.

Pierre Aboulker, Guillaume Aubian,
Pierre Charbit, Julien Duron, Colin Geniet, Emeric Gioan, Ararat Harutyunyan, Frédéric Havet, Florian Hoersch, Felix Klingelhoefer, William Lochet, Alantha Newman, Nicolas Nisse, Lucas Picasarri-Arrieta, Clément Rambaud, Stéphan Thomassé, Quentin Vermande.

Second ANR Digraph meeting

                  on-line June 15 – 18, 2021.

Programme :

Tuesday June 15

2pm : Frédéric Havet, Dichromatic number of surfaces.             Présentation

Abstract: The dichromatic number of a surface is the maximum dichromatic number of an oriented graph embedded in that surface. We give asymptotic bounds on the dichromatic number of a surface, and compute its exact value for some particular surfaces.
This is a joint work with Pierre Aboulker, Kolja Knauer, and Clément Rambaud.

3 pm : Frédéric Havet, Inversion in tournaments.                 Présentation

Abstract: Let D be an oriented graph. The inversion of a set X of vertices in D consists in reversing the direction of all arcs with both ends in X. The inversion number of D, denoted by inv(D), is the minimum number of inversions needed to make D acyclic. Denoting by tau(D), tau’ (D), and nu(D) the cycle transversal number, the cycle arc-transversal number and the cycle packing number of D respectively, one shows that inv(D) <= tau’ (D), inv(D) <= 2.tau(D) and there exists a function g such that inv(D)<= g(nu(D)).
We conjecture that for any two oriented graphs L and R, inv(L ra R) =inv(L) +inv(R) where L ra R is the dijoin of L and R. This would imply that the first two inequalities are tight. We prove this conjecture when inv(L)<= 1 and inv(R)<= 2 and when inv(L) =inv(R)=2 and L and R are strongly connected. We also show that the function g of the third inequality satisfies g(1)<= 4.

Wednesday June 16

2 pm : Pegah Pournajafi, Burling graphs revisited.         Présentation

Abstract: The Burling graphs form a class of triangle-free graphs with unbounded chromatic number. This class has attracted some attention because of its geometric representation and its importance in studying questions about chromatic number in hereditary classes of graphs. In this talk, we introduce some equivalent definitions of Burling graphs and then explain how one of these definitions can help us to find information about the structure of the graphs in this class.
This talk is based on joint work with Nicolas Trotignon. Some results are from

3 pm : Edouard Bonnet, Twin-width pour les graphes orientés.         Présentation

Abstract: La twin-width pour les graphes orientés est similaire à la twin-width ‘usuelle’ mais il y a des questions propres aux graphes orientés. Par ex: est-il vrai que pour les tournois la tww bornée correspond exactement à FO model checking en temps FPT? Ou encore comment se fait-il que les graphes extrémaux de CH, la conjecture qui ne doit pas être nommée, sont de twin-width bornée, etc…

4 pm : Open problems session

Friday June 18

9:30 am : Pierre Aboulker, Analogue of Gyárfás-Sumner conjecture for oriented graphs.         Présentation

Abstract: Gyarfás-Sumner Conjecture asserts that for every integer k and every forest T, the class of graphs with no clique on k vertices nor induced subgraphs isomorphic to T have bounded chromatic number. We will investigate an analogue of this conjecture for oriented graphs.
This is a joint work with Pierre Charbit and Reza Naserasr.

10:30 am  : Guillaume Aubian, Decomposition theorem for locally in-transitive tournaments.         Présentation
Abstract: A tournament is an orientation of a complete graph. A transitive tournament is an acylic tournament. An oriented graph is in-locally transitive if the in-neighborhood of each vertex is a transitive tournament.
We give a decomposition theorem for the class of locally in-transitive tournaments. As a consequence we obtain several applications, among which an answer to a Conjecture of Aboulker, Charbit and Naserasr about the dichromatic number, as well as a proof of the Caccetta–Häggkvist conjecture for this class.
This is a joint work with Pierre Aboulker and Pierre Charbit.

First ANR Digraph meeting

Seguret January 22 – 24, 2020.

Les commentaires sont clos.