Fifth ANR Digraph meeting
Sète May 30 – June 2, 2023.
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 : 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.
Third ANR Digraph meeting
Les Plantiers June 27 – July 3, 2022.
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 https://arxiv.org/abs/2104.07001.
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.
