This is a tentative program, there might still be some small changes.

All sessions will take place in Amphithéatre Gosse, ground floor of building C.

Click on the (+) next to the title of a talk to display the corresponding abstract.


9h15-10h00 registration and coffee

10h00-10h15 Myriam Preissmann - Introduction

10h15-11h00 András Gyárfás - Ramsey theory on Steiner triple systems (+) (slides)

A Steiner triple system, STS(`n`), is a set of `n>3` points together with `{n(n-1)}/ 6` triples, called blocks, that cover each pair of points exactly once. A configuration `C` (partial Steiner triple system, linear triple system) is a set of blocks pairwise intersecting in at most one point. An STS(`n`) is between the complete graph `K_n` and the complete 3-graph `K_n^3` so it is natural to ask Ramsey-type questions on them.

A configuration `C` is `k`-Ramsey if there exists `n_0=n_0(C,k)`, such that for `n\>= n_0` every `k`-coloring of the blocks of any STS(`n`) contains a monochromatic copy of `C`. The smallest `n_0` is `R(C,k)`, the `k`-color Ramsey number of `C`.

  • There are 5 configurations with three blocks, four of them acyclic. The fifth is the triangle, three pairwise intersecting blocks without a common point. All of them are `k`-Ramsey for every `k`. Guess `R(C,2)` where `C` is the triangle!
  • Among the 16 configurations with four blocks, two are not even 1-Ramsey (because they are avoidable) but 13 are `k`-Ramsey for every `k`.


11h15-11h45 Chính T. Hoàng - On color-critical graphs (+) (slides)

With respect to a hereditary class `cc C` of graphs, a `k`-chromatic graph `G in cc C` is said to be `k`-critical if every proper subgraph of `G` belonging to `cc C` is `(k-1)`-colorable. We show that there is a finite number of 4-critical `P_5`-free graphs. We construct an infinite set of `k`-critical `P_5`-free graphs for every `k >=5`. We show that for every fixed `k`, the number of `k`-critical (`P_5, bar {P_5}`) graphs is finite.

The results are joint work with B. Moore, D. Recoskie, J. Sawada, M. Vatshelle, H. S. Dhaliwal, A. M. Hamel, F. Maffray, T. J. D. McConnell, and S. A. Panait.

11h50-12h20 Yves Crama - Old and recent results on functions of Boolean variables (+) (slides)

Frédéric Maffray obtained his PhD in operations research at Rutgers University in 1989. Our common thesis adviser was the late Peter L. Hammer, who transmitted to both of us his interest in functions of Boolean variables and in their relation with other combinatorial structures. In this talk, I will recall some old results along those lines, and I will present some recent approaches to the optimization of multilinear polynomials in 0-1 variables.


14h-14h30 Aurélie Lagoutte - Decomposition techniques applied to the Clique-Stable set Separation problem (+) (slides)

In a graph, a Clique-Stable Set separator (CS-separator) is a family `C` of cuts (bipartitions of the vertex set) such that for every clique `K` and every stable set `S` disjoint from `K`, there exists a cut `(X,Y)` in `C` such that `K` is contained in `X` and `S` is contained in `Y`.

Starting from a question concerning extended formulations of the Stable Set polytope and a related complexity communication problem, Yannakakis asked in 1991 the following questions: does every graph admit a polynomial-size CS-separator? If not, does every perfect graph do? Several positive and negative results related to this question were given recently. Here we show how graph decomposition (clique cutset, module, ?) can be used to prove that a class of graphs admits a polynomial-size CS-separator. We apply this method to apple-free graphs and cap-free graphs.

Joint work with Frédéric Maffray, Nicolas Bousquet and Lucas Pastor

14h35-15h05 Dieter Rautenbach - LP based approximation of induced matchings (+) (slides)

A matching in a graph is induced if no two of its edges are joined by an edge, and finding a large induced matching is a very hard problem. Lin et al. (Approximating weighted induced matchings, Discrete Applied Mathematics 243 (2018) 304-310) provide an approximation algorithm with ratio `\Delta` for the weighted version of the induced matching problem on graphs of maximum degree `\Delta`. Their approach is based on an integer linear programming formulation whose integrality gap is at least `\Delta-1`, that is, their approach offers only little room for improvement in the weighted case. For the unweighted case though, we conjecture that the integrality gap is at most `\frac{5}{8}\Delta+O(1)`, and that also the approximation ratio can be improved at least to this value. We provide primal-dual approximation algorithms with ratios `(1-\epsilon) \Delta + \frac{1}{2}` for general `\Delta` with `\epsilon \approx 0.02005`, and `\frac{7}{3}` for `\Delta=3`. Furthermore, we prove a best-possible bound on the fractional induced matching number in terms of the order and the maximum degree.

15h10-15h40 Michael Tarsi - Bounded excess flows in cubic graphs (+) (slides)

An `(r,alpha)`-bounded excess flow (`(r,alpha)`-flow) in an orientation of a graph `G=(V,E)` is an assignment `f:E -> [1,r-1]`, such that for every vertex `x in V`, `|sum_{e in E^{+}(x)}f(e)-sum_{e in E^{-}(x)}f(e)| <= alpha`, where `E^+(x)`, respectively `E^{-}(x)`, are the sets of edges directed from, respectively toward `x`. Bounded excess flows suggest a generalization of Circular nowhere zero flows, which can be regarded as `(r,0)`-flows. `(r,\alpha)` is stronger or equivalent to `(s,beta)` if the existence of an `(r,alpha)`-flow in a cubic graph implies the existence of an `(s,beta)`-flow in the same graph. The structure of the bounded excess flow strength poset is studied and turns out to be rather involved.

A significant part of the talk is devoted to proving the main result: Every cubic graph admits a `(3 1/2,1/2)`-flow, and this bound is tight in terms of flow strength. This result is shown to be related to the famous 5-flow conjecture. A starting point for the proof is a joint recent result with L. Esperet and G. Mazzuoccolo.

16h00-17h30 Former Students session:

Benjamin Lévêque - Precoloring extension of co-Meyniel graphs (+) (slides)

The pre-coloring extension problem consists, given a graph `G` and a set of nodes to which some colors are already assigned, in finding a coloring of `G` with the minimum number of colors which respects the pre-coloring assignment. This can be reduced to the usual coloring problem on a certain contracted graph. We prove that pre-coloring extension is polynomial for complements of Meyniel graphs.We answer a question of Hujter and Tuza by showing that PrExt perfect graphs are exactly the co-Meyniel graphs, which also generalizes results of Hujter and Tuza and of Hertz. Moreover we show that, given a co-Meyniel graph, the corresponding contracted graph belongs to a restricted class of perfect graphs (co-Artemis graphs, which are co-perfectly contractile graphs), whose perfectness is easier to establish than the strong perfect graph theorem. However, the polynomiality of our algorithm still depends on the ellipsoid method for coloring perfect graphs.

Lucas Pastor (slides)

Nicolas Trotignon - Odd pairs of cliques (+) (slides)

In the times before the proof of the strong perfect conjecture, many attempts were made to find the best approach. An even pair is a pair of vertices such that all chordless paths linking them have even length. Meyniel proved that a minimally imperfect graph has no even pair. Therefore, to prove the strong perfect conjecture, it would be enough to prove that every Berge graph has an even pair. But this is obviously false, as shown by complete graphs and even anti holes. But these have even pairs in their complement. So, a better attempt might be to prove that every Berge graph has an even pair or an even pair in its complement. But again, it is false, and line graphs of bipartite graphs provides many counter examples. Since bipartite graphs on at least three vertices all have even pairs, one might wonder what happens to this even pair when going from the bipartite graph to its line graph. This lead Michel Burlet to the notion of odd pair of cliques. An odd pair of cliques in a graph `G` is a pair of cliques `K_1`, `K_2` such every chordless path with one end in `K_1`, one end in `K_2` and no internal vertex in `K_1 cup K_2` has odd length. Burlet conjectured that for every Berge graph `G`, one of `G` or the complement of `G` has an even pair or an odd pair of cliques. This is still open. In this talk, partial results about odd pairs of cliques in minimally imperfect graphs will be presented. They were obtained jointly with Frédéric Maffray and Michel Burlet at the beginning of my PhD. They were also obtained independently by András Sebö.


8h45-9h45 Jens Vygen - Ear-decompositions Meet T-joins: a Proof from The Book for a Theorem of Frank (videoconference from Cargese workshop)


10h15-10h45 Kristina Vušković - Coloring rings (+) (slides)

A ring `R` (of length `k`) is a graph whose vertex set can be partitioned into `k\geq 4` nonempty sets `X_1,\ldots ,X_k` such that for all `i\in \{ 1, \ldots ,k\}` the set `X_i` can be ordered as `X_i=\{ u_i^1, \ldots , u_i^{|X_i|}\}` so that `X_i\subseteq N[u_i^{|X_i|}]` `\subseteq` `\ldots \subseteq N[u_i^1] =X_{i-1}\cup X_i \cup X_{i+1}`. In particular, each `X_i` is a clique and every hole of `R` is of length `k`. It is easy to see that rings are a subclass of circular arc graphs, but that they are not necessarily proper circular arc (as they may contain claws). We observe that rings have unbounded clique-width. It is easy to see that if `v` is a vertex of a ring `R` then `R[N[v]]` and `R\setminus N[v]` are both chordal and hence the maximum weight clique problem and the maximum weight stable set problem can both be solved in polynomial time for rings. In this talk we show how to color rings in polynomial time. Rings whose length is even are perfect and quite easy to color. Coloring of rings whose length is odd turned out to be much more complicated.
This is joint work with Frédéric Maffray and Irena Penev.

10h50-11h20 Kathie Cameron - Finding an Easily Recognizable Strong Stable Set or a Meyniel Obstruction in any Graph (+) (slides)

I will speak about work done with Frédéric Maffray, Jack Edmonds, and Benjamin Lévêque. A stable set in a graph `G` is a set of vertices, no two of which are joined by an edge. A stable set in `G` is called strong if it contains a vertex of every maximal clique of `G`. This definition does not allow us to see easily that a stable set is strong; that is, it is not an NP-description. So instead we consider special strong stable sets called nice sets. A a nice set is a maximal stable set `S` linearly ordered so that there is no induced path on four vertices between any vertex `u` of `S` and the pseudonode obtained by identifying all vertices of `S` which precede `u`.

A Meyniel obstruction is an odd cycle with at least five vertices and with at most one chord. Given a graph `G` and a vertex `v` of `G`, we give a polytime algorithm to find either a nice set containing `v`, or a Meyniel obstruction in `G`. This can then be used to find in any graph, a clique and colouring of the same size or a Meyniel obstruction. We also give alternative approach which finds a colouring first.

11h25-12h10 Stéphan Thomassé - Quasi-polynomial time approximation schemes for Maximum Weight Independent Set Problem in H-free graphs (+)

We show that for every graph `H` for which Maximum Independent Set is not known to be APX-hard in `H`-free graphs, the problem admits a quasi-polynomial time approximation scheme in this graph class. Our algorithm works also in the more general weighted setting, where the input graph is supplied with a weight function on vertices and we are maximizing the total weight of an independent set.

Joint work with Maria Chudnovsky, Marcin Pilipczuk, and Michal Pilipczuk


13h45-16h30 Brazilian Session:

Former Brazilian Students sub-session

Cláudia Linhares - Even if it's hard, keep coloring (+) (slides)

In this seminar, I'm going to summarize my joint work with Frédéric Maffray about coloring through paires d'amis (couple of friends or even pair). Our main results were about friendship, explaining how paires d'amis can be used to color graphs. I'm going to remember our search, lots of them together with Bruce Reed, for paires d'amis in planar graphs, claw-free graphs, dart-free graphs and `C_4`-free graphs.

Ana Silva - Frédéric’s views on b-colorings (+) (slides)

I have had the honor and pleasure of being advised by Frédéric Maffray during my PhD from 2007 to 2010. Back then, we worked mainly on b-colorings of graphs that resembled trees. In this talk, I will present briefly his main contributions around b-colorings, which include many aspects of this type of colorings, such as continuity, perfection, and criticallity.

Break (14h30-14h50)

Victor Campos - Adapting The Directed Grid Theorem into an FPT Algorithm (+) (slides)

Originally proved in 1986 by Robertson and Seymour, the Grid Theorem is one of the most important tools in the field of structural graph theory, finding numerous applications in the design of algorithms for undirected graphs. An analogous version of the Grid Theorem in directed graphs was proved recently by Kawarabayashi and Kreutzer in 2015. In this talk, we adapt the proof of Kawarabayashi and Kreutzer into an FPT algorithm that, given a directed graph and an integer k, either finds an arboreal decomposition of width f(k) or returns a cylindrical grid of order k as a butterfly minor.

Sulamita Klein - The chain graph sandwich problem (+) (slides)

I will talk about the chain graph sandwich problem. This problem asks: Given a vertex set `V`, a mandatory set `E_1` and a larger set `E_2`, is there a graph `G=(V,E)`, such that `E_1 sube E sube E_2`, with `G` being a chain graph (i.e. a `2K_2`-free graph)? We studied this problem and proved that it is NP-complete, during a visit of Frederic Maffray to our group in Rio by the CAPES/COFECUB project. Simultaneously we were also having a visit of Martin Golumbic during his sabbatical, which gave us a great opportunity to work together.

Celina de Figueiredo - A tribute to thirty years of French Brazilian collaboration (+) (slides)

Frédéric Maffray fostered a fruitful thirty year collaboration that started with a workshop organized in 89 by Bruce Reed in Waterloo and was followed in 91 by a School on Perfect Graphs at the Federal University of Rio de Janeiro, where Alain Hertz and Frédéric Maffray gave the lectures. In 92, Cláudia Linhares went to Grenoble to be the first PhD student of Frédéric. Celina will give an overview of the 25 publications that Frédéric coauthored with Brazilians.

16h35 Testimonies and short (spontaneous) presentations, first half hour shared by videoconference with the Cargese workshop

19h00 DINNER


8h45-9h45 Jesús De Loera - Do linear programs dream of matroids when they sleep? (videoconference from Cargese workshop)


10h15-10h45 Adrian Bondy - Mind's Eye - linking mathematics and photography (+)

Mind's Eye is a French association whose goal is to find conceptual links between mathematics and photography. I founded the association after retiring from university. I will discuss its history and activities.


10h50-11h20 Gábor Bacsó - Forbidden trees and the beautiful trees of Grenoble (+) (slides)

We had two types of common research subjects with Frédéric.

The first type is in connection with the class Forb(`T`) of those graphs which do not contain a given tree `T` as an induced subgraph. We were looking for the properties of Forb(`T`). One can find a lot of such properties. The polynomiality of several originally NP-hard problems, many domination properties, `chi`-boundedness, and so on. À propos the last one, some partial results on a very old conjecture will also be discussed.

Questions concerning perfectness (algebraic structure and clique coloring, e.g.) represent the second type.

11h25-11h55- Ryan Hayward - Unsung Heroes of Hex (+) (slides)

In 1942 Piet Hein created the game of Polygon - now called Hex - and introduced it to the world via a series of puzzle columns in the Danish newspaper Politiken. Recently we discovered that Hein did not compose these beautiful puzzles, and identified some of the people who did.

This talk is based on a chapter of "Hex, the Full Story" by Hayward and Bjarne Toft.

12h00 Problem session


14h00-14h30 Frédéric Havet - On the unavoidability of trees in tournaments (+) (slides)

A digraph is `n`-unavoidable if it is contained in every tournament of order `n`. We first prove that every arborescence of order `n` with `k` leaves is `(n+k-1)`-unavoidable. We then prove that every oriented tree of order `n` (`n\geq 2`) with `k` leaves is `({3n}/2+{3k}/2 -2)`-unavoidable and `({9n}/2 -{5k}/2 -9/2)`-unavoidable, and thus `({21n}/8- 47/16)`-unavoidable. Finally, we prove that every oriented tree of order `n` with `k` leaves is `(n+ 144k^2 - 280k + 124)`-unavoidable.

This is joint work with François Dross.

14h35-15h20 Bruce Reed - Some Thoughts on Frédéric's Mathematics and Mathematical legacy (+)

This conference is a tribute to Frédéric Maffray and his Mathematics. Like many other speakers I will recall the work that I did with Frédéric throughout his career. This will include our decomposition theorem for claw-free perfect graphs. I will also discuss other aspects of his mathematics. This will be far from a full picture and will be biased towards the early days of his career.