2016 - 2017

---

Vendredi 9 septembre 2016 - Bootstrap Percolation in the Hypercube - Natasha Morrison (University of Oxford, UK).
The r-neighbour bootstrap process on a graph G starts with an initial set of ``infected'' vertices and, at each step of the process, a healthy vertex becomes infected if it has at least r infected neighbours (once a vertex becomes infected, it remains infected forever). If every vertex of G becomes infected during the process, then we say that the initial set percolates.

In this talk I will discuss the proof of a conjecture of Balogh and Bollobas: for fixed r and increasing d, the minimum cardinality of a percolating set in the d-dimensional hypercube is (1+o(1))/r*(d choose r-1). This is joint work with Jonathan Noel.

Vendredi 16 septembre 2016 - Combinatorial games on graphs - Éric Sopena (LaBRI)
Attention, ce séminaire aura lieu en A29 (rez-de-chaussée).
Après une entrée en matière dédiée à quelques notions de base de la théorie des jeux combinatoires (impartiaux), j’essaierai de vous proposer un « menu découverte », mêlant de façon réfléchie (notez bien le challenge !) les saveurs subtiles de résultats connus aux arômes alléchants de quelques problèmes ouverts en rapport avec différents jeux combinatoires sur des graphes. Pour le dessert, rien n’est arrêté à ce stade…

Vendredi 23 septembre 2016 - Lower bound on the treewidth of vital linkages in the plane - Frédéric Mazoit (LaBRI).
Let (s1, t1),..., (sk, tk) be distinct pair of vertices in a graph G. A linkage is a collection of paths P1,..., Pk such that each Pi links si and ti. A linkage is vital if it uses all the vertices of G and all linkages do so. Recently Adler and Krause gave an example of a planar graph with a vital linkage and with an exponential tree-width.

This implies that the Robertson and Seymour algorithm for solving the k-disjoint path problem on planar graphs is at least doubly exponential in k.

This result is also interesting because at first one would expect a polynomial bound. Then with the example, it is obvious the the bound is at least exponential. Then it is really not that clear the the example is indeed an example until one finally sees the proof which is quite simple and elegant.

Vendredi 30 septembre 2016 - Dessins non-alignés de graphes planaires - Claire Pennarun (LaBRI).
A "non-aligned" drawing of a graph is a drawing where no two vertices are in the same row or column. Auber et al. (2015) showed that not all planar graphs have a non-aligned planar straight-line drawing in the (n x n)-grid. They also showed that such a drawing exists if up to n-3 edges may have a bend.

In this talk, I will present three different algorithms for non-aligned planar drawings that improve on the results by Auber et al. In particular, I will give an example of such drawings in an (n x n)-grid with at most (2n-5)/3 bends, and I will show what grid-size can be achieved if one insists on having straight-line drawings.

Vendredi 7 octobre 2016 - On sum-free and solution-free sets of integers - Andrew Treglown (University of Birmingham, UK).
Given a linear equation L, a set A, which is a subset of [n], is L-free if A does not contain any 'non-trivial’ solutions to L. In the case when L is x+y=z, an L-free set is simply a sum-free set. In this talk we discuss a number of recent developments concering L-free sets.

In particular, we consider the following three general questions: (i) What is the size of the largest L-free subset of [n]? (ii) How many L-free subsets of [n] are there? (iii) How many maximal L-free subsets of [n] are there?

For example, together with Balogh, Liu and Sharifzadeh, we determine the number of maximal sum-free subsets of [n], thereby answering a question of Cameron and Erdős. Joint work with Robert Hancock will also be discussed.

Vendredi 14 octobre 2016 - Décomposition de graphes en 328 graphes localement irréguliers - Julien Bensmail (Université de Nice).
Afin d'étudier certains aspects de la 1-2-3 Conjecture, nous avons introduit, avec O. Baudon, J. Przybyło et M. Woźniak, la notion de décomposition en sous-graphes localement irréguliers. Il s'agit de partitionner les arêtes d'un graphe donné de sorte que chaque part induise un graphe localement irrégulier, i.e. sans paire de voisins ayant le même degré. Tous les graphes ne sont pas décomposables de cette manière, considérer, pour un exemple, un chemin de longueur impaire. Cependant, nous conjecturons que tout graphe décomposable se décompose en au plus trois sous-graphes localement irréguliers.

Jusqu'à récemment, nous ne savions pas montrer que pour une certaine constante c ≥ 3, tout graphe décomposable se décompose en au plus c sous-graphes localement irréguliers. Nous ne savions même pas le montrer pour les graphes bipartis décomposables. Avec M. Merker et C. Thomassen, nous avons pu prouver que tout graphe biparti décomposable se décompose en au plus c = 9 sous-graphes localement irréguliers. En combinant ce résultat et un résultat de Przybyło sur la décomposition de graphes de grand degré minimum, nous obtenons que tout graphe décomposable se décompose en au plus c = 328 sous-graphes localement irréguliers. Dans cet exposé, on présentera les arguments principaux permettant de prouver ces résultats.

Vendredi 21 octobre 2016 - Sensitivity complexity for graph properties - Ilan Karpas (Hebrew University of Jerusalem) .
The sensitivity complexity of f:{0,1}^n --> {0,1} at point x, is the number of coordinates i \in [n], so that changing the ith bit of x changes the value of the function f(x) \neq f(x^(i)). The sensitivity of f is then just the maximum sensitivity over all points x.

In 1984, Turan proved that the sensitivity complexity of any non-trivial graph property on n vertices, is at least n/4, n being the number of vertices. He conjectured that the true lower bound is n-1, which is known to be tight. In 2011, Sun improved the lower bound to 6n/11. I will sketch a proof for a lower bound on n/2.

Mercredi 26 octobre 2016 - From Tutte 3-flow conjecture to tree-partitions of graphs - Stéphan Thomassé (ENS de Lyon).
Does every sufficiently edge-connected graph have a nowhere zero 3-flow? This question of Tutte remained open for fifty years until Carsten Thomassen showed that 8-edge-connectivity is enough. I will review several generalizations of these questions (subset sums, cut sparsifiers and edge partitions of graphs) as well as recent results.

Joint work with: Julien Bensmail, Louis Esperet, Ararat Harutyunyan, Rémi de Joannis de Verclos, Tereza Klimošová, Tien-Nam Le and Martin Merker.

Vendredi 28 octobre 2016 - Symmetry-breaking polynomial - Paweł Petecki (AGH University, Pologne).
Let G be a graph, and let $\Gamma$ = Aut G. A coloring $c$ of G is symmetry-breaking if for every non-identity automorphism $\varphi \in \Gamma$ , there is some vertex $v$ of $G$ such that $c(v)\neq c(\varphi(v))$. There has been a lot of work on the minimum number of colors in a symmetry-breaking coloring of $G$. We discuss here a different problem: counting the number of k-colorings that are symmetry breaking. The tool, as is frequently the case for problems such as this one, is Möbius inversion. To solve this problem we define symmetry breaking polynomial $\psi_{G}$. For positive integer $k$ (number of colors), $\psi_G(k)$ is the number of k-colorings that break all non-trivial symmetries of the graph $G$.

Vendredi 4 novembre 2016 - Recolorer des homomorphismes de graphes via de la topologie élémentaire - Marcin Wrochna (University of Warsaw, Poland).
Nous considérons le problème dit de H-recoloration, défini comme suit pour un graphe H fixé. Étant donnés un graphe G et deux H-colorations de G (deux homomorphismes de G dans H), est-il possible de transformer l'une en l'autre en changeant la couleur d'un sommet de G à la fois ? Ceci généralise la question de recoloration classique, où, étonnamment, un algorithme polynomial a été exhibé par Cereceda et al. (2011) dans le cas de la 3-recoloration. Mon but sera de généraliser cet algorithme (en supposant H sans carré, c'est-à-dire, sans cycle de taille 4 comme sous-graphe), en essayant d'expliquer les intuitions topologiques derrière le résultat et les nouvelles questions qu'elles évoquent. Cet exposé ne suppose aucun pré-requis en topologie.

Vendredi 11 novembre 2016 - Férié

Vendredi 18 novembre 2016 - Pas de GT cause JGA

Vendredi 25 novembre 2016 - Cycles de partage dans les plongements des graphes complets - Vincent Despré (LaBRI).
Dans un graphe plongé sur une surface, un cycle de partage est un cycle qui sépare le plongement en 2 parties connexes de genre strictement plus petit que la surface de départ. Par exemple, un cycle de partage d'un graphe plongé sur un double-tore séparera la surface en 2 tores troués. En général, il n'est pas évident qu'un plongement donné contient un cycle de partage. Il a été conjecturé par Barnette que si le plongement était une triangulation alors il devait contenir un tel cycle. Je donnerai des contre-exemples à une version forte de cette conjecture. Ces contre-exemples utilisent les plongements des graphes complets qui ont servi a démontrer la conjecture de Heawood. Je donnerai aussi des détails au sujet de ce résultat de 1970 qui permet de démontrer l'équivalent du théorème des 4 couleurs pour les surfaces autres que le plan.

Vendredi 2 décembre 2016 - The k-matching cover problem: min-max relation and algorithm - Gautier Stauffer (G-SCOP, Grenoble).
A k-matching cover is a set of k (disjoint) matchings that cover all vertices of a graph. The k-matching cover problem is the problem of deciding whether a graph admits a k-matching cover and exhibit one in case it does. This is simply a perfect matching problem when k=1. For k>= 2, surprisingly the problem gets somewhat simpler and it is possible to prove an extension of Hall’s theorem in this case: a *general* graph (that does not admit a perfect matching) admits a k-matching cover with k>= 2 iff for all stable set S, we have |S| <= k |N(S)|. The proof builds upon Edmonds-Gallai Theorem and network flows and we can thus turn it into an efficient polytime algorithm. This is joint work with D. Ait-Ferhat and A. Sebo.

Vendredi 9 décembre 2016 - Gabriel Triangulations and Angle-Monotone Graphs: Local Routing and Recognition - Nicolas Bonichon (LaBRI).
A geometric graph is angle-monotone if every pair of vertices has a path between them that---after some rotation---is x- and y-monotone. Angle-monotone graphs are sqrt(2)-spanners and they are increasing-chord graphs. Dehkordi, Frati, and Gudmundsson introduced angle-monotone graphs in 2014 and proved that Gabriel triangulations are angle-monotone graphs. We give a polynomial time algorithm to recognize angle-monotone geometric graphs. We prove that every point set has a plane geometric graph that is generalized angle-monotone---specifically, we prove that the half-Theta_6 is generalized angle-monotone. We give a local routing algorithm for Gabriel triangulations that finds a path from any vertex s to any vertex t whose length is within 1+sqrt(2) times the Euclidean distance from s to t. Finally, we prove some lower bounds and limits on local routing algorithms on Gabriel triangulations.

Vendredi 16 décembre 2016 - Pique-nique et problèmes ouverts
Attention, ce sera à partir de 11h30 et pas 14h

Vendredi 13 janvier 2017 - Equitability, edge-injectivity, and the 1-2-3 Conjecture - Mohammed Senhaji (LaBRI).
Dans cette présentation on introduit le problème suivant : Pour un graphe simple non orienté G=(V,E), sans composante K_2, existe-t-il une pondération injective f:E → {1,... , |E|}, telle que ∀uv ∈ E, les sommets u et v sont distingués par la somme des poids de leurs arêtes incidentes ?

On y réponds par l'affirmatif dans le cas des forêts. Alors que pour d'autres familles de graphes creux ("sparse"), on s'autorise à utiliser un nombre constant de couleurs additionnelles. On prouve que cela est possible pour les graphes 2-dégénérés et de mad ≤ 3 (pour un graphe G, mad(G) désigne le maximum des degrés moyens de tous les sous-graphes de G).

Dans le cas des graphes en général, on obtient un résultat positif en utilisant 2.|E| ou |E|+2.Δ couleurs, où Δ est le degré maximum du graphe.

Vendredi 20 janvier 2017 - Tight lower bounds for the complexity of multicoloring - Marthe Bonamy (LaBRI).
In the multicoloring problem, also known as (a:b) or b-fold coloring, we are given a graph G and a set of a colors, and the task is to assign a subset of b colors to each vertex of G so that adjacent vertices receive disjoint color subsets. This natural generalization of the classic coloring problem (the b=1 case) is equivalent to finding a homomorphism to the Kneser graph with parameters a and b. It is tightly connected with the fractional chromatic number, and has multiple applications within computer science.

We study the complexity of determining whether a graph has an (a:b)-coloring. Nederlof showed in 2008 a (b+1)^n*Poly(n)-time algorithm for (a:b)-coloring. Our main result is that this is essentially optimal: there is no algorithm with running time 2^(o(log b)⋅n) unless the ETH fails. The crucial ingredient in our hardness reduction is the usage of detecting matrices of Lindström (1965), which is a combinatorial tool that, to the best of our knowledge, has not yet been used for proving complexity lower bounds.

This is joint work with Łukasz Kowalik, Michał Pilipczuk, Arkadiusz Socała and Marcin Wrochna (University of Warsaw). This talk is also meant as an introduction to proofs under ETH.

Vendredi 27 janvier 2017 - Recent results and techniques on the Erdős-Pósa property - Jean-Florent Raymond (LIRMM, Montpellier et MIMUW, Varsovie).
A classic result of Erdős and Pósa (1965) states that, for any positive integer k, either a graph contains k vertex-disjoint cycles, or a subset of O(k log k) vertices meets all its cycles. This initiated a quest for other objects where such a relation, called Erdős-Pósa property, holds between a parameter of packing (~ the maximum number of disjoint cycles) and one of covering (~ the minimum number of vertices meeting all cycles). This line of research has been subject to an increasing attention, which led to a wealth of results and variants. In this talk, I will give a general introduction to the topic and present its recent developments. I will also describe proof techniques and applications related to the Erdős-Pósa property.

Vendredi 3 février 2017 - Strong edge-colorings of sparse graphs with large maximum degree - André Raspaud (LaBRI).
A strong k-edge-coloring of a graph G is a mapping from E(G) to {1,2,.....,k} such that every two adjacent edges or two edges adjacent to the same edge receive distinct colors. In other words, the graph induced by each color class is an induced matching. This notion was introduced by Fouquet and Jolivet in 1983. The strong chromatic index chi_s'(G) off a graph G is the smallest integer k such that G admits a strong k-edge-coloring. In this talk we will give recent results about chi_s'(G) in terms of the maximum degree Delta(G) of a graph G when G is sparse, namely, when G is 2-degenerate or when the maximum average degree Mad(G) is small. We proved that the strong chromatic index of each 2-degenerate graph G is at most 5Delta(G) +1. Furthermore, we showed that for a graph G, if Mad(G)< 8/3 and Delta(G)>= 9, then chi_s'(G) <= 3Delta(G) -3 (the bound Delta(G) -3 is sharp) and if Mad(G)<3 and \Delta(G)\geq 7, then chi_s'(G)<= 3\Delta(G) (the restriction Mad(G)<3 is sharp). We will give some proofs during the talk. It is a joint work with I. Choi, J. Kim and A. Kostochka.

Vendredi 10 février 2017 - Une version quantique des jeux combinatoires - Paul Dorbec (LaBRI).
Dans cet exposé, nous étudierons des jeux combinatoires classiques, notamment le jeu de Nim, dans lesquels on fait évoluer les règles du jeu en autorisant à jouer des superpositions de coups. Nous verrons en quoi cette règle supplémentaire fait évoluer le jeu, mais aussi pourquoi cela peut être pertinent pour améliorer l'intuition des situations modélisées par la physique quantique.

Vendredi 17 février 2017 - Bounded palette list coloring - Marthe Bonamy (LaBRI).
Attention, ce séminaire aura exceptionnellement lieu de 15h30 à 16h30 (toujours en 178).
Bounded palette list coloring is an intermediary notion between standard coloring and list coloring. We say that a graph is (k,p)-choosable if for every assignment L of k colors to each vertex that involves at most p different colors on the whole, the graph is L-colorable. This corresponds to standard coloring when k=p, and to list coloring when p is infinite. Does there exist some function C such that every (k,p)-choosable graph is C(k,p)-choosable? If so, what does it look like? This talk is meant as a discussion of counter-intuitive facts on bounded palette list coloring, including our result answering a 2005 question of Kral and Sgall. This is joint work with Ross Kang (Radboud University Nijmegen).

Vendredi 24 février 2017 - Vacances

Vendredi 3 mars 2017 - On a generalization of nonrepetitive sequences - Martina Mockovčiaková (KMA, Plzeň).
A sequence is called nonrepetitive or Thue if it does not contain a repetition of any length. Currie and Simpson introduced a generalization of this notion.
A sequence S is k-Thue if every j-subsequence of S is Thue, for 1≤ j≤k. Here, a j-subsequence of S is a subsequence ξiξi+j ξi+2j. . . , for any i.
In 2002 Grytczuk conjectured that k + 2 symbols are enough to construct a k-Thue sequence of arbitrary length and it was shown that the conjecture is true for k = 2, 3 and 5.
We present a construction of arbitrarily long k-Thue sequences on 2k symbols, which improves the previous bound of 2k + 10√k. Moreover, we confirm the conjecture for the cases k = 4 and 6 in two ways and present constructions of both cases using 6 and 8 symbols, respectively.
Additionaly, we define cyclic k-Thue sequences and show that four symbols suffice to construct a cyclic 2-Thue sequence of any length, with three exceptions. As a corollary, we obtain a tight bound on total Thue coloring of cycles.

Vendredi 10 mars 2017 - Pas de GT cause soutenance de thèse Noël Gillet.

Vendredi 17 mars 2017 - On the density of sets avoiding parallelohedron distance 1 - Philippe Moustrou (LaBRI & IMB).
In this joint work with C. Bachoc, T. Bellitto and A. Pêcher, we study the density of sets avoiding distance 1 in R^n. Let ||.|| be a norm on R^n. We consider the so-called unit distance graph G associated with ||.|| : the vertices of G are the points of R^n, and the edges connect the pairs {x,y} satisfying ||x-y||=1. We define m_1(R^n,||.||) as the supremum of the densities achieved by independent sets in G. The number m_1 was introduced by Larman and Rogers (1972) as a tool to study the measurable chromatic number chi_m(R^n) of R^n for the Euclidean norm. However, determining m_1(R^n,||.||_2) is still a difficult problem. We study this problem for norms whose unit ball is a convex polytope. More precisely, if the unit ball corresponding with ||.|| tiles R^n by translation, then it is easy to see that m_1(R^n,||.||) >= 1/2^n. C. Bachoc and S. Robins conjectured that equality always holds. We show that this conjecture is true for n=2 and for some polytopes in higher dimensions.

Vendredi 24 mars 2017 - Decompositions of cubic graphs into an induced tree and a stable set - František Kardoš (LaBRI).
In this talk, we will present a sufficient condition for a cubic graph to decompose into and induced tree and a stable set, due to Payan and Sacharevich (1975). We will discuss several applications of this classical result in the proofs of Hamiltonicity of various classes of cubic graphs, and some related open problems.

Vendredi 31 mars 2017 - Pas de GT.

Vendredi 7 avril 2017 - Robustness in Highly Dynamic Networks - Arnaud Casteigts (LaBRI).
We investigate a special case of hereditary property that we refer to as robustness. A property is robust in a given graph if it is inherited by all connected spanning subgraphs of this graph. We motivate this definition in different contexts, showing that it plays a central role in highly dynamic networks, although the problem is defined in terms of classical (static) graph theory. In this paper, we focus on the robustness of maximal independent sets (MIS). Following the above definition, a MIS is said to be robust (RMIS) if it remains a valid MIS in all connected spanning subgraphs of the original graph. We characterize the class of graphs in which all possible MISs are robust. We show that, in these particular graphs, the problem of finding a robust MIS is local; that is, we present an RMIS algorithm using only a sublogarithmic number of rounds (in the number of nodes n) in the LOCAL model. On the negative side, we show that, in general graphs, the problem is not local. Precisely, we prove a Ω(n) lower bound on the number of rounds required for the nodes to decide consistently in some graphs. This result implies a separation between the RMIS problem and the MIS problem in general graphs. It also implies that any strategy in this case is asymptotically (in order) as bad as collecting all the network information at one node and solving the problem in a centralized manner. Motivated by this observation, we present a centralized algorithm that computes a robust MIS in a given graph, if one exists, and rejects otherwise. Significantly, this algorithm requires only a polynomial amount of local computation time, despite the fact that exponentially many MISs and exponentially many connected spanning subgraphs may exist.

Vendredi 14 avril 2017 - Pas de GT.

Vendredi 21 avril 2017 - Vacances.

Vendredi 28 avril 2017 - On augmenting matchings via bounded-length augmentations - Julien Bensmaïl (I3S, Nice).
In a graph, it is well-known that a matching can be turned into a bigger matching by applying a so-called augmentation operation. Due to a classical result of Berge, by repeatedly applying this operation, we actually necessarily end up with a maximum matching. Nisse, Salch and Weber considered the influence on this fact of restricting the length k of the augmented paths. In particular, they proved that, for k=3, reaching, via augmentations of (≤k)-paths, a maximum matching from an initial matching can be done in polynomial time for any graph, while the same problem for any odd k≥5 is NP-complete. The latter result remains true for bipartite graphs, while we still have no clue for trees. Nisse, Salch and Weber nevertheless exhibited a polynomial-time algorithm solving this problem for any path. In a recent work with Garnero and Nisse, we made some progress towards understanding this problem for general trees. In particular, we have exhibited polynomial-time solving algorithms for a few more tree classes, including bounded-degree trees, caterpillars, subdivided stars, and trees where the vertices with degree at least 3 are sufficiently far apart. We have also obtained some negative results for modified versions of the problem. During this talk, we will present the proofs of some of these results, and mention some remaining open questions.

Jeudi 4 mai 2017 - Polynomial expansion and sublinear balanced separators - Jean-Florent Raymond (LIRMM, Montpellier et MIMUW, Varsovie).
Let C be a subgraph-closed class of graphs. Dvořák and Norin proved that graphs in C have sublinear balanced separators iff the density of any depth-k minor of a graph of C (i.e. minor obtained by contracting disjoint subgraphs of radius at most k) can be upper-bounded by a polynomial in k. They conjectured that if the balanced separators in C have size O(n^{1−δ}) (for some 0 < δ ≤ 1), then any depth-k minor of a graph of C has density O(k^{c/δ}), for some constant c. We prove this conjecture. This is joint work with Louis Esperet.

Vendredi 12 mai 2017 - Vertex-distinguishing edge coloring - Hervé Hocquard (LaBRI).
An adjacent vertex-distinguishing edge coloring (AVD coloring) of a graph is a proper edge coloring such that no two neighbors are incident to the same set of colors. Zhang et al. conjectured that every connected graph on at least 6 vertices is AVD (Delta+2)-colorable, where Delta is the maximum degree. In this talk, we prove that (Delta+1) colors are enough when Delta is sufficiently larger than the maximum average degree, denoted mad. We also provide more precise lower bounds for two graph classes: planar graphs, and graphs with mad<3. In the first case, Delta>=12 suffices, which generalizes the result of Edwards on planar bipartite graphs and strengthens the result of Hornak et al. that (Delta+2) is enough. In the second case, Delta>=4 is enough, which is optimal and completes the results of Wang and Wang and of Hocquard and Montassier. We also will present recent results on neighbor sum distinguishing coloring.

Vendredi 26 mai 2017 - Pont.

Jeudi 1 juin 2017 - Gendarmes, voleurs et topologie algébrique - David Ellison (RMIT, Melbourne).
Le jeu du gendarme et du voleur, introduit par Alain Quilliot dans sa thèse en 1978, est un jeu à deux joueurs sur un graphe. Le gendarme commence en choisissant son point de départ sur un sommet du graphe ; puis le voleur choisit le sien. Ensuite, ils se déplacent chacun leur tour le long des arêtes du graphe. La question est de savoir si le gendarme a une stratégie qui lui permet d'attraper le voleur. Dans le cas contraire, la question devient : combien faut-il de gendarmes pour attraper le voleur ? Quilliot a démontré dans sa thèse qu'un seul gendarme suffit à attraper le voleur si et seulement si le graphe est démontable, c'est-à-dire si et seulement si on peut le réduire à un seul sommet en retirant successivement des sommets où le voleur peut être coincé. Il s'ensuit que les graphes démontables correspondent à la classe d'homotopie du point, et que certains invariants homotopiques, comme les groupes d'homologie, permettent de découvrir des propriétés structurelles des graphes où le gendarme peut attraper le voleur.

Vendredi 2 juin 2017 - Pas de GT cause journée d'équipe.

Mercredi 14 juin 2017 - Soutenance de thèse - Claire Pennarun (LaBRI).
Attention, ce sera dans l'amphi du LaBRI. (mais bien à 14h)

Jeudi 15 juin 2017 - Total Domination in Graphs and Transversals in Hypergraphs - Michael A. Henning (University of Johannesburg).
The total domination number of a graph G is the minimum cardinality of a set S of vertices so that every vertex of G is adjacent to a vertex in S, while the transversal number of a hypergraph H is the minimum cardinality of a subset of vertices in H that has a nonempty intersection with every edge of H. Much of the recent interest in total domination in graphs arises from the fact that total domination in graphs can be translated to the problem of finding transversals in hypergraphs since the transversal number of the open neighborhood hypergraph of a graph is precisely the total domination number of the graph. We explore this transition from total domination in graphs to transversals in hypergraphs and discuss several recent results on total domination in graphs obtained using transversals in hypergraphs that appear difficult to obtain using purely graph theoretic techniques. For example, we prove the conjecture that if G is a quadrilateral-free graph with minimum degree at least 4, then the total domination number is at most two-fifths the order. In order to prove this result, we first prove some key results on transversals in linear hypergraphs, as well as results on matchings in graphs.

Vendredi 23 juin 13h !! - Identification de points dans le plan par des disques - Valentin Gledel (Université Claude Bernard Lyon 1).

On considère le problème d'identification de n points du plan par des disques, c'est à dire minimiser le nombre de disques tels que chaque point est contenu dans au moins un disque et qu'il n'y ait pas de paire de points contenu par exactement le même ensemble de disques. Ce problème peut être vu comme une instance du problème d'identification par dans des hypergraphes avec des contraintes géométriques sur les hyperarêtes. Nous donnons une borne haute et une borne basse sur le nombre de disques nécessaire pour identifier n points en position quelconque, toutes les deux atteintes, et améliorons la borne haute lorsqu'il n'y a pas trois points alignés ou quatre points cocycliques, qui est exacte à une constante près. Nous étudions aussi la complexité du problème lorsque le rayon des disques est fixé, prouvant qu'il est NP-complet dans le cas général et qu'il peut être résolu en temps linéaire lorsque les points sont tous alignés.

Vendredi 23 juin 2017 - Coloring, sparseness, and girth - Xuding Zhu (Zhejiang Normal University Jinhua, China).
An r-augmented tree is a rooted tree plus r edges added from each leaf to ancestors. For d, g, r in N, we construct a bipartite r-augmented complete d-ary tree having girth at least g. The height of such trees must grow extremely rapidly in terms of the girth. Using the resulting graphs, we construct sparse non-k-choosable bipartite graphs, showing that maximum average degree at most 2(k − 1) is a sharp sufficient condition for k-choosability in bipartite graphs, even when requiring large girth. We also give a new simple construction of non-k-colorable graphs and hypergraphs with any girth g. This is a joint work with Noga Alon, Alexandr Kostochka, Benjamin Reiniger and Douglas B. West.

Vendredi 30 juin 2017 - Pique-nique + Exposés Tom Davot et Paul Ouvrard (LaBRI).

10h - Coloration par multi-sommes - Tom Davot.
La coloration par multi-sommes est une généralisation de trois types de coloration des arêtes d’un graphe : la coloration par sommes, la décomposition en sous-graphe localement irréguliers et la coloration par multi-ensembles. Le principe de cette coloration est de donner un poids entre 1 et q et une couleur entre 1 et p à chaque arête d’un graphe, puis pour chaque sommet, faire la somme des poids des arêtes d’une même couleur incidentes à ce sommet de façon à obtenir un p-uplet pour chaque sommet, où chaque composante de ce $p$-uplet correspond à une couleur. On souhaite ensuite distinguer les p-uplets de deux sommets voisins, différentes variantes pouvant être utilisées pour faire cette distinction. Dans cette présentation, nous verrons des résultats de la coloration par multi-sommes pour les cycles, les graphes complets et les graphes scindés dans une variante dite standard.

10h30 - Reconfiguration d’ensembles dominants par token sliding - Paul Ouvrard.
Dans cet exposé, nous nous intéressons à la reconfiguration d'ensembles dominants par token sliding. Étant donné un graphe $G$ et deux ensembles dominants $A$ et $B$ de ce graphe, nous souhaitons savoir s'il est possible de transformer, étape par étape à l'aide de mouvements élémentaires la solution $A$ en la solution $B$. De plus, il est primordial que la notion de dominant soit préservée à chaque étape intermédiaire. Dans la littérature, trois principaux mouvements élémentaires ont été étudiés : token addition and removal (TAR), token jumping (TJ) et token sliding (TS). À ce jour, si de nombreux résultats de reconfiguration considèrent la coloration ou le problème d’ensemble stable comme problème de base, il y a encore peu de résultats dans le cadre de la reconfiguration de dominants. Haddadan et al. se sont récemment intéressés à ce problème sous le modèle du token jumping. Nous présentons ici des résultats algorithmiques et de complexité pour la reconfiguration d'ensembles dominants par token sliding.

Vendredi 14 juillet 2017 - Férié.

Vendredi 28 juillet 2017 - Edge-partitioning graphs into paths and trees - Tereza Klimošová (Charles University, Prague).
In 2006, Barat and Thomassen conjectured that for a fixed tree T, every sufficiently edge-connected graph with the number of edges divisible by |E(T)| has a T-decomposition. That is, the edge set of the graph can be partitioned into isomorphic copies of T. The conjecture was recently proven by Bensmail, Harutyunyan, Le, Merker and Thomasse. Bensmail, Harutyunyan, Le, and Thomasse posed a strengthened version of the conjecture of Barat and Thomassen, that for a fixed tree T, every graph with sufficiently high minimum degree and with the number of edges divisible by |E(T)| has a T-decomposition if it is sufficiently highly edge-connected in terms of maximal degree of T. They proved the strengthened conjecture for T being a path. The talk will contain several extensions of the results above. We give the optimum edge-connectivity bound of the strengthened version of Barat-Thomassen conjecture for paths and we disprove the conjecture for trees of maximal degree at least three. We also prove a version of the conjecture for "coprime forests", that is, forests consisting of two vertex disjoint forests with coprime numbers of edges. Joint work with Stephan Thomasse.