Les GT se tiennent chaque vendredi de 14h à 15h en salle 178. Vous êtes invités à venir 10 minutes avant pour partager thé, café et gâteaux.

Pour vous inscrire à la liste de diffusion, il suffit d'envoyer un mail à sympa@diff.u-bordeaux.fr avec pour sujet "subscribe labri.go-gt Cookie Monster", où Cookie est remplacé par votre prénom et Monster par votre nom.

Prochains exposés :

Mardi 3 juillet 2018 - Increasing the Matching Preclusion Number from 1 to 2 - Moritz Mühlenthaler (TU Dortmund University).
The matching preclusion number of a graph is the minimal number of edges whose removal destroys all perfect matchings. We provide algorithms and hardness results for the task of increasing the matching preclusion number from one to two in bipartite graphs at minimal cost. Our motivation is to make matchings of a graph robust against the failure of a single edge. Our methods rely on a close relationship to the classical strong connectivity augmentation problem. For the unit weight problem we provide a deterministic $\log_2 n$-factor approximation algorithm, as well as polynomial-time algorithms for graphs of bounded treewidth and chordal-bipartite graphs. For general weights we prove a dichotomy theorem characterizing minor-closed graph classes which allow for a polynomial-time algorithm.

Mercredi 4 juillet 2018 - Enumerating colourings via clique-width and colour renaming - Michael Raskin (LaBRI).
Graph colourings are studied for many different reasons and from many different points of view. Courcelle's theorem allows to enumerate the graph colourings of bounded-clique-width graphs in linear (in the size of the graph, but not clique-width or number of colours) time.

In the talk I will show how to apply the symmetry between colours to improve the performance of the colouring enumeration with clique-width representation.

Jeudi 5 juillet 2018 15h30 - DP-coloring - Seog-Jin Kim (University of Konkuk).
DP-coloring was introduced by Dvorak and Postle (2015) to study list coloring. DP-coloring of a graph is a generalization of list coloring, and also a generalization of signed coloring of signed graphs. In this talk, we will give an overview of DP-coloring, and present recent results in DP-coloring.

Vendredi 6 juillet 2018 - AG LaBRI + barbecue.

Mercredi 11 juillet 2018 10h - Maximum Scatter TSP in Doubling Metrics - Tobias Mömke (Universität Bremen).

We study the problem of finding a tour of n points in which every edge is long. More precisely, we wish to find a tour that visits every point exactly once, maximizing the length of the shortest edge in the tour. The problem is known as Maximum Scatter TSP, and was introduced by Arkin et al. (SODA 1997), motivated by applications in manufacturing and medical imaging. Arkin et al. gave a 0.5 -approximation for the metric version of the problem and showed that this is the best possible ratio achievable in polynomial time (assuming P !=NP). Arkin et al. raised the question of whether a better approximation ratio can be obtained in the Euclidean plane.

We answer this question in the affirmative in a more general setting, by giving a (1-epsilon)-approximation algorithm for d-dimensional doubling metrics, with running time \tilde{O}(n^^3 + 2^(O(K log K))), where K <= ( 13/epsilon)^d. As a corollary we obtain (i) an efficient polynomial-time approximation scheme (EPTAS) for all constant dimensions d, (ii) a polynomial-time approximation scheme (PTAS) for dimension d = (log log n)/c, for a sufficiently large constant c, and (iii) a PTAS for constant d and epsilon = Omega(1/log log n). Furthermore, we show the dependence on d in our approximation scheme to be essentially optimal, unless Satisfiability can be solved in subexponential time.

Mardi 17 juillet 2018 10h00 - Structural Parameterization of Geometric Intersection Graphs - Dibyayan Chakraborty (Indian Statistical Institute, Kolkata, India).
Consider a geometric intersection graph class which is NP-Hard to recognise. What can be a "natural" approach to study the structure of such classes? In this presentation, we propose such an approach and talk about the success (and failures) when applied on Rectangle Intersection graphs (it is NP-Hard to recognise such graphs). We shall introduce a parameter called "stab number" of rectangle intersection graphs and study the structure of those with "low stab number". We shall see how this parameter can be used to obtain necessary conditions for a graph to have a rectangle intersection representation.

Mardi 17 juillet 2018 11h00 - A brief overview of oriented coloring and its variants - Sagnik Sen (RamaKrishana Mission Educational and Research Institute, Kolkata, India).
Vertex coloring of a graph $G$ with $n$-colors can be equivalently thought to be a graph homomorphism (edge preserving vertex mapping) of $G$ to the complete graph $K_n$ of order $n$. So, in that sense, the chromatic number $\chi(G)$ of $G$ will be the order of the smallest complete graph to which $G$ admits a homomorphism to. As every graph, which is not a complete graph, admits a homomorphism to a smaller complete graph, we can redefine the chromatic number $\chi(G)$ of $G$ to be the order of the smallest graph to which $G$ admits a homomorphism to. Of course, such a smallest graph must be a complete graph as they are the only graphs with chromatic number equal to their order. Using the notion of graph homomorphism the concept of vertex coloring can be generalized for oriented graphs, that is, directed graphs without cycles of length at most 2.

Using graph homomorphism or otherwise, researchers have defined analogous versions of different other coloring related problems and parameters, namely, cliques, edge coloring, total coloring, fractional coloring, list coloring, complete coloring etc. for oriented graphs and studied their different aspects. In this talk we will give a brief overview on homomorphism and coloring of oriented graphs, present some open questions in this domain and mention some of our results as part of it.

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

Amphitéâ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 14 septembre 2018 - Soutenance de thèse de Mohammed Senhaji.

Amphithéâtre du LaBRI, à 14h00. 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).