Lundi 27 août 2018 - Soutenance de thèse de Thomas Bellitto.

Amphithéâtre du LaBRI, à 10h. Titre de la thèse : *Walks, Transitions and Geometric Distances in Graphs*.
Jury : Christine Bachoc (directeur de thèse) - Jørgen Bang-Jensen (rapporteur) - Sylvain Gravier (rapporteur) - Mickael Montassier (examinateur) - Arnaud Pêcher (directeur de thèse) - Éric Sopena (examinateur).

Vendredi 7 septembre 2018 - Proportionally dense subgraph of maximum size: complexity and approximation - Clément Dallard (University of Portsmouth, Royaume-Uni).

We define a proportionally dense subgraph (PDS) as an induced subgraph of a graph with the property that each vertex in the PDS is adjacent to proportionally as many vertices in the subgraph as in the graph. We prove that the problem of finding a PDS of maximum size is NP-hard, more precisely APX-hard, even on split graphs. On the other hand, we present a simple polynomial-time (2 - (2/(Δ+1)))-approximation algorithm for the problem, where Δ is the maximum degree in the graph. We also prove that all Hamiltonian cubic graphs (except two) have a PDS of the maximum possible size which can be found in linear time (if a Hamiltonian cycle is given) and sketch the proof. Finally, we show that deciding if a PDS is inclusion-wise maximal is co-NP-complete on bipartite graphs.

Vendredi 14 septembre 2018 - Soutenance de thèse de Mohammed Senhaji.

Amphithéâtre du LaBRI, à 14h. Titre de la thèse : *Neighbour-distinguishing decompositions of graphs*.
Jury : Maria Axenovich et Alexandre Pinlou (rapporteurs) - Aline Parreau, Arnaud Pêcher, Olivier Baudon et Eric Sopena (examinateurs).

Vendredi 21 septembre 2018 - Maximum Independent Set in H-free graphs - Édouard Bonnet (LIP, Lyon).

Maximum Independent Set (MIS) in graphs without a connected H as an induced subgraph (that is, H-free) is NP-complete when H is not a tree with at most one vertex of degree at least 3. For the other graphs H, which are paths and subdivisions of the claw (K_1,3), the computational complexity of MIS is generally open except for a small number of cases. We will explore the parameterized complexity of MIS in H-free graphs. Our distant goal is to establish a dichotomy of the H for which the problem can be solved in time f(k)n^{O(1)} and the ones for which such an algorithm is unlikely to exist (where n is the total number of vertices, k is the size of the solution, and f is any computable function). Recast in the parameterized complexity language, we want to know when the problem is FPT and when it is W[1]-complete. We will present a selection of results and draw a parallel with the situation for the 'classical dichotomy' (P/NP-complete). This is joint work with Nicolas Bousquet, Pierre Charbit, Stéphan Thomassé, and Rémi Watrigant.

Vendredi 28 septembre 2018 - Coloring the squares of planar graphs with no 4-cycle - Théo Pierron (LaBRI).

Coloring the square of a graph consists in assigning colors to its vertices in such a way that any two vertices at distance at most 2 receive different colors. While D+1 colors are needed to properly color the square of any graph of maximum degree D, Wegner proved that there is no hope for a matching upper bound of D+O(1) in general, even for planar graphs. We study the cycle obstructions needed to obtain such a bound for planar graphs. We present here the case where only finitely many cycles lengths are forbidden. In this setting, we prove that removing only cycles of length 4 is necessary and sufficient to obtain the desired bound. For very large D, we also improve a result of Bonamy, Cranston and Postle by showing that D+2 colors are always sufficient for coloring the square of C_4-free planar graphs, which is tight. This is joint work with Ilkyoo Choi and Daniel W. Cranston.

Mercredi 10 octobre 2018 15h - salle 76 - Rapid mixing of Glauber dynamics for colorings below Vigoda’s 11/6 threshold - Michelle Delcourt (University of Waterloo, Canada).

A well-known conjecture in computer science and statistical physics is that Glauber dynamics on the set of $k$-colorings of a graph $G$ on $n$ vertices with maximum degree $\Delta$ is rapidly mixing for $k \geq \Delta+2$. In 1999 Vigoda showed rapid mixing time of a modified version of flip dynamics for $k >11/6 \Delta$, implying polynomial time mixing for Glauber dynamics under the same constraints. This conjecture has attracted a lot of attention in the literature and better results are known for certain classes of graphs. In this talk, we improve Vigoda's bound for general graphs by showing that there exists a constant $\eta>0$ such that the Glauber dynamics mixes in polynomial time for $k \geq (11/6- \eta)\Delta$. Our proof combines path coupling with a new kind of metric we introduce to incorporate a count of the extremal configurations of the chain. This "extremal" metric proves to be much easier to analyze than stopping-time-based metrics, and hence we believe will have fruitful applications for bounding the mixing times of other Markov chains. This is joint work with Guillem Perarnau and Luke Postle.

Vendredi 19 octobre 2018 - On the density of critical graphs without large cliques - Tom Kelly (University of Waterloo, Canada).

A graph is k-critical if it has chromatic number k and every proper subgraph is (k - 1)-colorable. The density of critical graphs has been extensively studied. We present an improvement on the best known lower bound for the density of critical graphs without large cliques. We also discuss a connection to list-coloring and generalizations of Reed's Conjecture.

Joint work with Luke Postle.

Vendredi 26 octobre 2018 - Claw-free matroids - Peter Nelson (University of Waterloo, Canada).

Let M be a set of nonzero vectors in a vector space over the two-element field. We say that M is claw-free if there are no vectors x, y, z in M for which x+y, y+z, x+y, x+y+z are not in M. These objects are a matroidal/geometric analogue of claw-free graphs. I will discuss a theorem, obtained recently with Kazuhiro Nomoto, that exactly classifies all claw-free M.

Lundi 5 novembre 2018 à 15h30 - Acyclic Colouring of Graphs on Surfaces - Shayla Redlin (University of Waterloo, Canada).

An acyclic k-colouring of a graph G is a proper k-colouring of G with no bichromatic cycles. In 1979, Borodin proved that planar graphs are acyclically 5-colourable, an analog of the Four Colour Theorem. Kawarabayashi and Mohar proved in 2010 that "locally" planar graphs are acyclically 7-colourable, an analog of Thomassen's result that "locally" planar graphs are 5-colourable. We say that a graph G is critical for (acyclic) k-colouring if G is not (acyclically) k-colourable, but all proper subgraphs of G are. In 1997, Thomassen proved that for every k >= 5 and every surface S, there are only finitely many graphs that embed in S that are critical for k-colouring. Here we prove the analogous result that for all k >= 12 and each surface S, there are finitely many graphs embeddable on S that are critical for acyclic k-colouring. This result implies that there exists a linear time algorithm that, given a surface S and large enough k, decides whether a graph embedded in S is acyclically k-colourable.

Mardi 6 novembre 2018 à 15h - Density and Structure of Homomorphism-Critical Graphs - Evelyne Smith-Roberge (University of Waterloo, Canada).

Let $H$ be a graph. A graph $G$ is $H$-critical if every proper subgraph of $G$ admits a homomorphism to $H$, but $G$ itself does not. In 1981, Jaeger made the following conjecture concerning odd-cycle critical graphs: every planar graph of girth at least $4t$ admits a homomorphism to $C_{2t+1}$ (or equivalently, has a $\tfrac{2t+1}{t}$-circular colouring). The best known result for the $t=3$ case states that every planar graph of girth at least 18 has a homomorphism to $C_7$. We improve upon this result, showing that every planar graph of girth at least 16 admits a homomorphism to $C_7$. This is obtained from a more general result regarding the density of $C_7$-critical graphs. Our main theorem is that if $G$ is a $C_7$-critical graph with $G \not \in \{C_3, C_5\}$, then $e(G) \geq \tfrac{17v(G)-2}{15}$. In this talk, I will go over the history of the progress towards Jaeger's conjecture, and give a general overview of the proof structure of our main theorem. Along the way, I will prove several structural lemmas concerning graphs that are $H$-critical, when $H$ is a vertex-transitive non-bipartite graph.

Vendredi 9 novembre 2018 - Labeling schemes for trees and planar graphs - Paweł Gawrychowski (University of Wrocław, Poland).

Labeling schemes seek to assign a label to each node in a network, so that a function on two nodes can be computed by examining their labels alone. The goal is to minimize the maximum length of a label and (as a secondary goal) the time to evaluate the function. As a prime example, we might want to compute the distance between two nodes of a network using only their labels. We consider this question for two natural classes of networks: trees and planar graphs. For trees on n nodes, we design labels consisting of 1/4log^2(n) bits (up to lower order terms). Interestingly, our solution circumvents a lower bound of 1/2log^2(n) obtained for a natural class of schemes based on the so-called universal graphs. I will discuss how a related notion of minor-universal graphs allows us to significantly improve on the best known bounds for NCA labeling.

For planar graphs, the situation is much more complex. A major open problem is to close the gap between an upper bound of O(n^{1/2}log(n))-bits and a lower bound of O(n^{1/3})-bits for unweighted planar graphs. We show that, for undirected unweighted planar graphs, there is no hope to achieve a higher lower bound using the known techniques. This is done by designing a centralized structure of size ~O(min(k^2,(kn)^{1/2})) that can calculate the distance between any pair of designated k terminal nodes. We show that this size it tight, up to polylogarithmic terms, for such centralized structures. This is complemented by an improved upper bound of O(n^{1/2}) for labeling nodes of an undirected unweighted planar graph for calculating the distances.

Vendredi 7 décembre 2018 - à partir de 11h30 - Pique-nique et exposé de Michał Pilipczuk.

Vendredi 7 décembre à 14h - Progressive algorithms for distance domination in sparse graphs. - Michał Pilipczuk (University of Warsaw, Poland).

In the distance-r dominating set problem we are given a graph G and integers r and k, and the question is whether G can be covered with k balls of radius r. We present a new, generic approach to the problems that gives a simple, linear-time fixed-parameter tractable algorithm (i.e. with running time f(r,k) * n) on a whole spectrum of sparse graph classes; more precisely, on any graph class that is nowhere dense. This topic will serve as an excuse to give an introduction to the theory of structural sparsity, an active research area originating in the work of Nesetril and Ossona de Mendez which provides a variety of combinatorial and algorithmic tools for working with sparse graphs.