Vendredi 7 juillet à 14h - Tara Abrishami
The central bag method
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed
In this talk we explain the central bag method, which is an approach to analyzing the structure of hereditary graph classes. The central bag method works by iteratively decomposing a graph using special collections of separations. In addition to the details of the central bag method, we will discuss applications of the method to proving bounded treewidth results and to finding poly-time algorithms to solve the maximum weight independent set problem.

Vendredi 30 juin à 14h - Alp Muyesser
Random embeddings with optimal spread
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed
Let G and H be graphs on n vertices, and suppose G has large enough minimum degree to necessarily contain H as a subgraph. We show that H in fact embeds into G with good ``spread''. More precisely, for a wide class of H, we find a randomised embedding f:H->G with the following property: for every s, for any partial embedding f' of s vertices of H into G, the probability that f extends f' is at most O(1/n)^s. This is a common generalisation of several streams of research surrounding the classical Dirac-type problem.

For example, setting s=n, we obtain an asymptotically tight lower bound on the number of embeddings of H on G. This recovers and extends recent results of Montgomery and Pavez-Signé regarding enumerating Hamilton cycles in Dirac graphs. Moreover, using the recent developments surrounding the Kahn-Kalai conjecture, this result implies that many Dirac-type results hold robustly, meaning H still embeds into random sparsifications of the edge-set of G. In particular, we recover recent results of Kang-Kelly-Kühn-Osthus-Pfenninger and Pham-Sah-Sawhney-Simkin for perfect matchings, and obtain novel results for Hamilton cycles and graph factors.

In this talk, we present our randomised embedding algorithm, which is simple and self-contained. Notably, the algorithm does not rely on the regularity/absorption method, unlike similar results in the area.

This is joint work with Tom Kelly and Alexey Pokrovskiy.

Vendredi 23 juin à 14h - Edgar Baucher
Un premier pas vers les graphes universels isométriques
Les Graphes Universels Isométriques, qui vont de pair avec les Distance Labeling, peuvent être utilisés pour répondre à des questions d'optimisation de flux de données pour des algorithmes distribués, notamment lorsqu'on veut connaître la distance entre des sommets d'un graphe. Étant donné une famille de graphe F, un Graphe Universel Isométrique de F est un graphe qui contient tous les graphes de F en tant que sous-graphe isométrique, c'est à dire que pour tout graphe G de F, on peut retrouver G comme un sous-graphe du Graphe Universel Isométrique de F tel que toutes les distances entre les sommets de G sont les mêmes dans G et dans ce sous-graphe. L'objectif est en général de trouver le Graphe Universel Isométrique le plus petit (en terme de nombre de sommets) pour une famille donnée, ce qui laisse place à des problèmes allant de triviaux à NP-complets et de "amusant" à "à s'arracher les cheveux pour celles et ceux qui en ont encore".

Dans cet exposé, nous nous intéresserons à certaines propriétés structurelles et algorithmiques des Graphes Universels Isométriques. Ces graphes étant à ce jour très peu étudiés dans la recherche, nous nous intéresserons aussi aux liens qu'ils ont avec les Distance Labeling, qui sont eux plus étudiés.

Vendredi 9 juin à 14h - Marthe Bonamy
Some open problems
In this talk, we will survey some open problems in graph theory, from graph minors to subgraph packing, including a few coloring questions. This selection will be extremely biased, with an attention to diversity of flavours.

Vendredi 23 mai à 14h - Yaping Mao
Steiner Tree Packing Problem
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed
Steiner tree is popularly used in the physical design of VLSI circuits and network science. Steiner tree is also used in computer communication networks and optical wireless communication networks. For a given graph G and a vertex subset S, the problem that asks to find a set of maximum number of edge-disjoint Steiner trees connecting S of G is called the Steiner tree packing problem, which studies local properties of graphs or networks. Generalized (edge-)connectivity is an Steiner tree packing parameter, which focuses on global properties of graphs or networks.

In this talk, we present the computational complexity and some known results of generalized connectivity. We also introduce recent progress of Kriesell Conjecture on Steiner tree packing problem and West-Wu Conjecture on S-connectors.

Vendredi 5 mai à 14h - Lucas Picasarri-Arrieta
Recolouring digraphs with bounded maximum degree
Connexion: https://webconf.math.cnrs.fr/b/mar-zjd-6dz
A dicolouring of a digraph is a partition of its vertex-set into acyclic subsets. This notion extends the notion of proper colourings of an undirected graph. In the context of digraph recolouring, given a digraph and two of its dicolourings, we wonder if we can transform one into the other by recolouring one vertex at each step while maintaining a dicolouring at any step. Moreover, when such a recolouring sequence exists, we look for the shortest one. We will consider these questions when dealing with digraphs of bounded maximum degree. In particular, we extend a result due to Feghali et al. and improve this result when restricted to oriented graphs. In order to achieve this, we show a strengthening of the Directed Brooks' Theorem when restricted to this particular class of digraphs.

Vendredi 13 avril à 13h - Jozef Skokan
On the chroamtic profiles of graphs
(in English) Contact Clément Legrand-Duchesne for the recording
Let F be a fixed family of graphs. The chromatic profile of F is a function of c defined as the infimum of those α for which every F-free n-vertex graph of minimum degree α n has chromatic number bounded by c.

In other words, the chromatic profile measures how large the minimum degree needs to be in order to guarantee that an F-free graph has chromatic number at most c. Erdös and Simonovits judged that in full generality this quantity seemed ‘too complicated’ to study. Despite considerable progress in the last few decades, this judgment still stands firm. The goal of this talk is to discuss this further.

Vendredi 6 avril à 14h - Cyril Gavoille
On the Freeze-Tag Problem
(In French, slides in English) Contact Claire Hilaire for the recording
We consider the problem of awaking as fast as possible and by contacts a swarm of asleep robots, starting with only one awake robot. In this talk, we will review the main results for this problem, in particular for the euclidean plane, and also give some recent contributions.

This is a joint work with Nicolas Bonichon, Arnaud Casteigts, and Nicolas Hanusse.

Vendredi 24 mars à 14h - Laura Merker
Outerplanar directed acyclic graphs have constant stack number
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed
The stack number of a directed acyclic graph G is the minimum k for which there is a topological ordering of G and a k-coloring of the edges such that no two edges of the same color cross, i.e., have alternating endpoints along the topological ordering. We prove that the stack number of directed acyclic outerplanar graphs is bounded by a constant, which gives a positive answer to a conjecture by Heath, Pemmaraju and Trenk [SIAM J. Computing, 1999]. As an immediate consequence, this shows that all upward outerplanar graphs have constant stack number, answering a question by Bhore et al. [GD 2021] and thereby making significant progress towards the problem for general upward planar graphs originating from Nowakowski and Parker [Order, 1989]. As our main tool we develop the novel technique of directed H-partitions, which might be of independent interest.

We complement the bounded stack number for directed acyclic outerplanar graphs by constructing a family of directed acyclic 2-trees that have unbounded stack number, thereby refuting a conjecture by Nöllenburg and Pupyrev [arXiv:2107.13658, 2021].

In this talk we introduce the concepts of stack layouts and directed H-partitions and sketch some of the techniques and proofs.

Joint work with Paul Jungeblut and Torsten Ueckerdt.

Vendredi 17 mars à 14h - Alexandra Wesolek
Cops and Robber Game on Surfaces of Euclidean, Spherical and Hyperbolic Metric
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed
Recently, Mohar introduced a variant of the cops and robber game that is played on geodesic spaces. The game combines properties of pursuit-evasion games with the classical cops and robber game played on graphs. In this talk we discuss the rules of the game and strategies for the players when the game is played on compact surfaces of constant curvature 0,1 and -1. Joint work with Vesna Iršič and Bojan Mohar.

Vendredi 10 mars à 14h - James Davies
Two structural results for pivot-minors
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed
Pivot-minors can be thought of as a dense analogue of the graph minor relation. We shall discuss pivot-minors and two recent results for proper pivot-minor-closed classes of graphs. In particular, that for every graph H, the class of graphs containing no H-pivot-minor is chi-bounded, and also satisfies the (strong) Erdős-Hajnal property.

Vendredi 3 mars à 14h - Clara Marcille
On inducing degenerate sums through 2-labellings
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed
We deal with a variant of the 1-2-3 Conjecture introduced by Gao, Wang, and Wu in [Graphs and Combinatorics, 32:1415-1421, 2016]. This variant asks whether all graphs can have their edges labelled with 1 and 2 so that when computing the sums of labels incident to the vertices, no monochromatic cycle appears. In the aforementioned seminal work, the authors mainly verified their conjecture for a few classes of graphs, namely graphs with maximum average degree at most 3 and series-parallel graphs, and observed that it also holds for simple classes of graphs (cycles, complete graphs, and complete bipartite graphs).

In this talk, we provide a deeper study of this conjecture, establishing strong connections with other, more or less distant notions of graph theory. While this conjecture connects quite naturally to other notions and problems surrounding the 1-2-3 Conjecture, it can also be expressed so that it relates to notions such as the vertex-arboricity of graphs. Exploiting such connections, we provide easy proofs that the conjecture holds for bipartite graphs and 2-degenerate graphs, thus generalising some of the results of Gao, Wang, and Wu. We also prove that the conjecture holds for graphs with maximum average degree less than 10/3, thereby strengthening another of their results.

Vendredi 17 février à 14h - Freddie Illingworth
Minimum degree stability and locally colourable graphs
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed
We tie together two natural but, a priori, different themes. As a starting point, consider Erdős and Simonovits's classical edge stability for an (r + 1)-chromatic graph H. This says that any n-vertex H-free graph with (1 − 1/r + o(1))*(n choose 2) edges is close to (within o(n^2) edges of) r-partite. This is false if 1 − 1/r is replaced by any smaller constant. However, instead of insisting on many edges, what if we ask that the n-vertex graph has large minimum degree? This is the basic question of minimum degree stability: what constant c guarantees that any n-vertex H-free graph with minimum degree greater than cn is close to r-partite? c depends not just on chromatic number of H but also on its finer structure.

Somewhat surprisingly, answering the minimum degree stability question requires understanding locally colourable graphs -- graphs in which every neighbourhood has small chromatic number -- with large minimum degree. This is a natural local-to-global colouring question: if every neighbourhood is big and has small chromatic number must the whole graph have small chromatic number? The triangle-free case has a rich history. The more general case has some similarities but also striking differences.

Vendredi 10 février à 14h - Amadeus Reinald
Twin-width and polynomial kernels
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed
Twin-width is a graph invariant recently introduced by Bonnet, Kim, Thomassé and Watrigant [FOCS'20]. The core result of their paper states that, on classes of bounded twin-width, deciding any problem expressible by a first-order logic formula φ is FPT with respects to |φ|. Bounded twin-width classes are very diverse, and plenty of decision problems such as k-Independent Set, k-Dominating Set and k-Vertex Cover can be expressed in first order, yielding their fixed-parameter tractability on these classes. In this talk, we investigate the existence of polynomial kernels for k-Vertex Cover and k-Dominating Set on classes of bounded twin-width. In these classes, we start by showing a (sub)quadratic kernel k-Vertex Cover. After introducing the background required for kernel lower bounds, we present our main result, that k-Dominating Set admits no polynomial kernel on classes of twin-width at most four. Joint work with Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé and Rémi Watrigant [Algorithmica, https://arxiv.org/abs/2107.02882].

Vendredi 3 février à 14h - François Dross
Approximation Schemes for finding multicolored non-crossing structures in the plane and in planar graphs
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed
In this presentation, we will talk about connecting colored points via noncrossing structures. Several problems fall into this category. Given a set of colored terminal points, we want to find a graph for each color that connects all terminals of its color with the restriction that no two graphs cross each other. We will look for such graphs with certain specific structure. If the graph is not restrained (or restrained to be a tree), the problem is Multicolored Non-crossing Steiner Tree. If the graph is a cycle, the problem is Multicolored Non-crossing Travelling Salesman Problem... We will consider these problems both on the Euclidean plane and in planar graphs. Another linked problem that we will talk about is the problem of separating colored points in the plane accoring to their colors, using non-crossing cycles.

The aim of this talk will be to present a method to approximate these problems efficiently, when there is a small number of colors (two or three, depending on the problem). The trick relies on a way to bound the number of times a given area in the plane, that we will call portal, needs to be crossed when there are two colors. The rest of the proof heavily relies on Arora's scheme, that we will also present. We may also have time to talk about the negative side, and, more precisely, complexity results.

Vendredi 27 janvier à 14h - Fábio Botler
Separating the edges of a graph by a linear number of paths
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed
A path separates an edge e from an edge f if it contains the former and not the latter. How many paths do we need to separate any edge from any other? This question was first asked by Katona in 2013, in line with the general study of separating systems initiated by Rényi in 1961. In this talk, we show that the answer is linear in the number of vertices, thus confirming a conjecture independently posed by Balogh, Csaba, Martin, and Pluhár and by Falgas-Ravry, Kittipassorn, Korándi, Letzter, and Narayanan. We focus on the proof method and possible extensions.
This is based on joint work with Bonamy, Dross, Naia and Skokan.

Vendredi 20 janvier à 14h - František Kardoš
Subcubic planar graphs of girth 7 are class I
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

We prove that planar graphs of maximum degree 3 and of girth at least 7 are 3-edge-colorable, extending the previous result for girth at least 8 by Kronk, Radlowski, and Franen from 1974.
This is a joint work with Sebastien Bonduelle.
https://doi.org/10.1016/j.disc.2022.113002

Vendredi 13 janvier à 14h - Paul Bastide
Graph reconstruciton with distance oracles
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed
(in English)
How fast can you reconstruct a network using a ping-pong protocol. Distance query reconstruction is a setting where we assume an unknown simple and connected graph, and we try to recover the graph only using queries of distance between pairs of vertices. In this talk we extend a result by Kannan, Mathieu, and Zhou in the probabilistic settings, creating a randomized algorithm able to reconstruct graphs of bounded treelength with a quasi-linear number of queries in expectation. In particular, graphs of bounded treewidth contain various graph classes of interest such as k-chordal graphs, permutation graphs and AT-free graphs. This talk is based on a joint work with Carla Groenland.

Vendredi 9 décembre à 14h - Fábio Botler
Mod k colorings of graphs
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed
(in English)
Given a positive integer k, a mod k coloring of a graph G is a coloring of the edges of G in which each color induces a graph whose non-isolated vertices have degree congruent to 1 (mod k). The mod k coloring problem is to minimize the number of colors used in a mod k coloring of G. In 1997, Scott proved that every graph G admits a mod k coloring with at most 5k^2 log k colors. In this talk we will show that this bound can be reduced to 198k-101.

Vendredi 2 décembre à 14h - Cyril Gavoille
Smaller Universal Graphs for Caterpillars and Graphs of Bounded Path-Width, Part 2
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed
(in French, English slides)
In this talk, I will given a rather simple construction of a graph U_n with at most 8n vertices with the property that every n-vertex caterpillar is isomorphic to some induced-subgraph of U_n. Previous constructions of so-called induced-universal graph for caterpillars used 256n vertices in the best (Bonichon et al. SIROCCO'06 and Alstrup et al. FOCS'15).

Then, I will also present an extension to path-width-p graphs with an induced-universal graph of n.2^O(p) vertices. This is complemented with a n.2^Ω(p) lower bound. With bounded path-width graphs, our construction considerably enlarge the family of n-vertex graphs having an induced-universal graph of O(n) vertices, which is optimal. Such unexpected property was known only for trees, bounded maximum degree outerplanar graphs and maximum degree-2 graphs.

The extended result is obtained from an algorithmic approach by designing an adjacency labeling scheme for these graphs using log(n) + O(p) bit vertex labels and with a constant time adjacency test.

This is a joint work with Arnaud Labourel.

Vendredi 25 novembre à 14h - Clément Legrand-Duchesne
Recoloring planar graphs with Kempe changes
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

Given a coloring of a fixed graph G, a Kempe chain is a maximal bichromatic connected component. A Kempe change is a recoloring operation consisting in swapping the two colors inside a Kempe chain. Meyniel proved in 1978 that any two 5-colorings of a planar graph are equivalent up to a series of O(5^|V(G)|) Kempe changes. We strengthen this result, by proving that any two 5-colorings of a planar graph are equivalent up to a polynomial number of Kempe changes. This is a first step towards bounding polynomially the diameter of the reconfiguration graph of d-degenerate graphs.

Vendredi 28 octobre à 14h - James Davies
Odd distances in colourings of the plane
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

We prove that every finite colouring of the plane contains a monochromatic pair of points at an odd distance from each other. This resolves Rosenfeld's odd distance problem.

Vendredi 21 octobre à 14h - Paul Bastide
Exact antichain saturation numbers via a generalisation of a result of Lehman-Ron
Only offline, no online version
in French, English slides
For given positive integers k and n, a family F of subsets of {1,...,n} is k-antichain saturated if it does not contain an antichain of size k, but adding any set to F creates an antichain of size k. We use sat*(n, k) to denote the smallest size of such a family. For all k and sufficiently large n, we determine the exact value of sat*(n, k), which confirms several conjectures on antichain saturation. Previously, exact values for sat*(n,k) were only known for k up to 6. We also prove a strengthening of a result of Lehman-Ron which may be of independent interest. We show that given m disjoint chains in the Boolean lattice, we can create $m$ disjoint skipless chains that cover the same elements (where we call a chain skipless if any two consecutive elements differ in size by exactly one).

Vendredi 14 octobre à 14h - Claire Hilaire
Structure of graphs with bounded induced cycle packing number
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed
(in French, English slides)
A graph is Ok-free if it does not contain k pairwise vertex-disjoint and non-adjacent cycles. We show that sparse (here, not containing large complete bipartite graphs as sub-graphs) Ok-free graphs have treewidth (even, feedback vertex set number) at most logarithmic in the number of vertices. This is proven sharp as there is an infinite family of O2-free graphs without K3,3-subgraph and whose treewidth is (at least) logarithmic. This result implies that most of the central NP-complete problems (such as Maximum Independent Set, Minimum Vertex Cover, Minimum Dominating Set, Minimum Coloring) can be solved in polynomial time in sparse Ok-free graphs, and that deciding the Ok-freeness of sparse graphs is polynomial time solvable.

This is a joint work with Marthe Bonamy, Édouard Bonnet, Hugues Déprés, Louis Esperet, Colin Geniet, Stéphan Thomassé, and Alexandra Wesolek.

Vendredi 7 octobre à 14h - Cyril Gavoille
Smaller Universal Graphs for Caterpillars and Graphs of Bounded Path-Width
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed
(in French, English slides)
In this talk, I will given a rather simple construction of a graph U_n with at most 8n vertices with the property that every n-vertex caterpillar is isomorphic to some induced-subgraph of U_n. Previous constructions of so-called induced-universal graph for caterpillars used 256n vertices in the best (Bonichon et al. SIROCCO'06 and Alstrup et al. FOCS'15).

Then, I will also present an extension to path-width-p graphs with an induced-universal graph of n.2^O(p) vertices. This is complemented with a n.2^Ω(p) lower bound. With bounded path-width graphs, our construction considerably enlarge the family of n-vertex graphs having an induced-universal graph of O(n) vertices, which is optimal. Such unexpected property was known only for trees, bounded maximum degree outerplanar graphs and maximum degree-2 graphs.

The extended result is obtained from an algorithmic approach by designing an adjacency labeling scheme for these graphs using log(n) + O(p) bit vertex labels and with a constant time adjacency test.

This is a joint work with Arnaud Labourel.

Vendredi 30 septembre à 13h - Péter Pál Pach
The Alon-Jaeger-Tarsi conjecture via group ring identities
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

The Alon-Jaeger-Tarsi conjecture states that for any finite field F of size at least 4 and any nonsingular matrix A over F there exists a vector x such that neither x nor Ax has a 0 component. In this talk we discuss the proof of this result for primes larger than 61 and further applications of our method about coset covers and additive bases. Joint work with János Nagy and István Tomon.

Vendredi 23 septembre à 14h - Michael Savery
Induced subgraphs of induced subragphs of large chromatic number
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

What structure can be found in a graph G with large chromatic number? One possibility is that G contains a large clique, but if it does not, then can we find an induced subgraph of G which still has fairly large chromatic number but is simpler than G in some way? In this talk we will discuss some limitations of this approach. We will prove that for every graph F with at least one edge there are graphs G of arbitrarily large chromatic number and the same clique number as F such that every induced subgraph of G with chromatic number at least c = c(F) contains an induced copy of F. This generalises recent theorems of Briański, Davies, and Walczak, and of Carbonero, Hompe, Moore, and Spirkl. We will also outline how to show an analogous statement where clique number is replaced by odd girth. This is joint work with António Girão, Freddie Illingworth, Emil Powierski, Alex Scott, Youri Tamitegama, and Jane Tan.

Vendredi 9 septembre à 14h - Jane Tan
Exploring comparable box dimension
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

Two boxes in R^d are comparable if one of them is a subset of a translation of the other. The comparable box dimension of a graph G is the minimum d such that G can be represented as a touching graph of comparable axis-aligned boxes in R^d. Having finite comparable box dimension implies a number of nice graph properties, which leads us to consider which graphs have such geometric representations. In this talk, we show that comparable box representations behave well under several common operations on graphs. This leads to a proof that every proper minor-closed class of graphs has finite comparable box dimension. Based on joint work with Zdeněk Dvořák, Daniel Goncalves, Abhiruk Lahiri and Torsten Ueckerdt.