We will provide a brief overview of principal graph classes of graphs from Metric Graph Theory: median graphs, bridged (alias systolic) graphs, Helly graphs, hyperbolic graphs, partial cubes, weakly modular graphs, basis graphs of matroids, dual polar graphs, and tope graphs of oriented matroids. For some classes we will present metric or local-to-global characterizations and properties. Some of those classes will be subjects of more detailed talks.

Nous évoquons la notion de lignes dans les espaces d'alignement qui prend sa source dans les travaux de Chen et Chvatal au début du millénaire. La question principale consiste à déterminer la portabilité de la propriété de de Bruijn-Erdös aux espaces métriques généraux (et aux métriques de graphes en particulier). Nous verrons un état des lieux des travaux en cours et des questions ouvertes intéressantes.

We introduce notions of certificates allowing to bound eccentricities in a graph. In particular, we revisit radius (minimum eccentricity) and diameter (maximum eccentricity) computation and explain the efficiency of practical radius and diameter algorithms by the existence of small certificates for radius and diameter plus few additional properties. We show how such computation is related to covering a graph with certain balls or complementary of balls. We introduce several new algorithmic techniques related to eccentricity computation and propose algorithms for radius, diameter and all eccentricities with theoretical guarantees with respect to certain graph parameters. This is complemented by experimental results on various real-world graphs showing that these parameters appear to be low in practice. We also obtain refined results in the case where the input graph has low doubling dimension, has low hyperbolicity, or is chordal.

Joint work with Feodor Dragan and Michel Habib.

In this talk, we will present a simple factor $8$ approximation algorithm for computing Gromov hyperbolicity of an $n$-vertex unweighted graph $G = (V,E)$ in optimal time $O(n^2)$ (given the distance matrix of $G$ as the input). This algorithm leads to constant factor approximations of other graph-parameters related to hyperbolicity: thinness, slimness, and insize. This is a joint work with Jérémie Chalopin, Victor Chepoi, Feodor Dragan, Guillaume Ducoffe and Abdulhakeem Mohammed.

Acyclic orientations of a graph, linear extensions of a poset, hyperplane arrangements, linear dissections of polyhedra, pseudoline arrangements... all of these can be seen as (complexes of) oriented matroids (COMs). The tope graph of a COM is a graph capturing all the information of this potentially quite complex object. In the above examples it corresponds to: the flip graph of acyclic orientations (two are linked by an edge if they differ in one arc), the linear extension graph of a poset (two are linked if they differ by one neighboring transposition), the region graphs of any of the other examples. In this talk, I will explain all these concepts carefully. Finally we will give a purely graph theoretic characterization of tope graphs of COMs, which furthermore is polytime verifyable. This answers a kind of central question in Oriented Matroid Theory and in a sense identifies the latter as a branch of Metric Graph Theory. Based on joint work with Hans-Jürgen Bandelt, Victor Chepoi, and Tilen Marc.

Given a graph G and a subgraph H of G, we can wonder whether G admits a perfect H-packing, i.e. whether we can partition the vertices of G into (induced) copies of H. A classical example of such a question is whether a graph admits a perfect matching. There does not seem to be any good sufficient conditions for G to admit a perfect H-packing. Here, we investigate when a sufficiently high Cartesian power of G admits a perfect H-packing. We generalize a theorem of Gruslys for hypercubes to powers of even cycles, and disprove a conjecture of Gruslys as well as one by Gruslys, Leader and Tan that considers the edge setting. This type of questions has ramifications far beyond the scope of graph theory. This is joint work with Natasha Morrison and Alex Scott.

For an integer q >=2 and an even integer d, consider the graph obtained from a large complete q-ary tree by connecting with an edge any two vertices at distance exactly d in the tree. This graph has clique number q+1. The goal of this talk is to prove that its chromatic number is at least d

  \log q / \log d.

It was not known that the chromatic number of this graph grows with d. As a simple corollary of our result, we give a negative answer to a problem of van den Heuvel and Naserasr, asking whether there is a constant C such that for any odd integer d, any planar graph can be colored with at most $C$ colors such that any pair of vertices at distance exactly $d$ have distinct colors.

A pair of metric spaces ((X,d), (Y,d')) is Kirszbraun if any 1-Lipschitz (nonexpansive) map f:A-->X from any subset A of X can be extended to a nonexpansive map from X to Y. We will recall some classical results: (1) characterization of Kirszbraun pairs ((X,d), (Y,d')) (F. Valentine, 1943); (2) characterization of hyperconvexity (i.e. of geodesic Helly spaces) via Kirszbraun property (N. Aronszajn, P. Panitchpakdi, 1956); (3) (E^n,E^m) is Kirszbraun (the Kirszbraun theorem, 1934) and some new newer results (4) Kirszbraun property for Gromov hyperbolic geodesic spaces and graphs (U. Lang, 1999) (5) characterization of all graphs G such that (Z^n,G) is Kirszbraun (N. Chandgotia, I. Pak, M. Tassy, 2017) .