2014 - 2015

Vendredi 19 septembre 2014 - AVD coloring - Hervé Hocquard.
Résumé : 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.

Vendredi 3 octobre 2014 - (f,g)-alliance auto-stabilisante avec convergence sûre - Yvan Rivierre.
Résumé : Les (f,g)-alliances sont des structures couvrantes généralisant plusieurs notions de la théorie des graphes qui sont largement utilisées dans le domaine des systèmes répartis, parmi lesquelles figurent les ensembles dominants, les ensembles k-dominants, les ensembles k-tuples dominants, les alliances défensives et les alliances offensives. Lorsque ces notions interviennent dans le cadre d'un système réparti à grande échelle, il est nécessaire de prendre en compte les pannes dans la conception des protocoles qui les mettent en œuvre. Un algorithme est dit auto-stabilisant s'il garantit à un système réparti de retrouver, après avoir été perturbé par des fautes transitoires et sans intervention extérieure, un fonctionnement normal en un temps fini. Ce temps peut être important selon le type de problème auquel répond l'algorithme. La convergence sûre vise à pallier cet écueil de l'auto-stabilisation en garantissant un minimum de sûreté de fonctionnement en un temps plus court voire constant.

Dans cet exposé, nous considérerons la notion de (f,g)-alliance et ses liens avec les autres notions précitées. Nous étudierons le problème de construction auto-stabilisante d'une (f,g)-alliance et nous proposerons un algorithme auto-stabilisant avec convergence sûre construisant une (f,g)-alliance minimale si f ≥ g.

Vendredi 10 octobre 2014 - La méthode des atomes en théorie des graphes et en théorie des nombres - Gilles Zémor. Exposé spécial CPU/Axe 3
Résumé : Les atomes d'un graphe ont été introduits pour étudier leur connectivité. Depuis, la méthode atomique ou isopérimétrique a été transposée en combinatoire additive pour obtenir des caractérisations d'ensembles de petite somme dans les groupes. Nous passerons en revue ces connexions et aborderons une application récente, obtenue avec Oriol Serra et Christine Bachoc, sur la caractérisation, dans des extensions de corps, d'espaces vectoriels dont le produit a une petite dimension.

Vendredi 7 novembre 2014 - On Colouring Games - Elżbieta Sidorowicz (University of Zielona Góra).
Résumé : Let be given a graph $G$ and a set $C$ of $r$ colours. Two players, Alice and Bob alternately colour a vertex of $G$ in such a way that two adjacent vertices are not coloured with the same colour. Alice has the first move. If after $|V(G)|$ moves the graph is properly coloured, then Alice wins, otherwise Bob wins. The above game is called the $r$-colouring game. The game chromatic number of $G$ is the least number $r$ for which Alice has a winning strategy for the colouring game with $r$ colours on $G$. In this talk we will discuss some version of the colouring game and we will give winning strategies for Alice to play these games. We also will present upper bounds for the game chromatic numbers for some families of graphs.

Vendredi 14 novembre 2014 - Locally irregular graph colourings - Jakub Przybyło.
Résumé : It is well known that there are no \emph{irregular graphs}, understood as simple graphs with pairwise distinct vertex degrees, except the trivial $1$-vertex case. A graph invariant called the \emph{irregularity strength} was thus introduced aiming at capturing a level of irregularity of a graph. Suppose that given a graph $G = (V,E)$ we wish to construct a multigraph with pairwise distinct vertex degrees of it by multiplying some of its edges. The least $k$ so that we are able to achieve such goal using at most k copies of every edge is denoted by $s(G)$ and referred to as the irregularity strength of $G$. Alternately one may consider (not necessarily proper) edge colourings $c: E\to\{1,2,\ldots,k\}$ with $\sum_{e\ni u}c(e)\neq\sum_{e\ni v}c(e)$ for every pair of distinct vertices $u,v \in V$. Then the least $k$ which permits defining a colouring $c$ with this feature equals $s(G)$. Numerous papers have been devoted to study on this graph invariant since the middle 80's.

On the other hand, there are many \emph{locally irregular graphs}, i.e., those whose only \emph{adjacent} vertices are required to have distinct degrees. Analogously as above one might also measure how far a given graph $G=(V,E)$ is from being locally irregular. That is, how large $k$ is needed in order to define an edge colouring $c: E\to\{1,2,\ldots,k\}$ with $\sum_{e\ni u}c(e)\neq\sum_{e\ni v}c(e)$ for every pair of adjacent vertices $u,v$ of $G$. It is believed that already $k=3$ is sufficient for all graphs containing no isolated edges. This suspicion is commonly referred to as the 1--2--3--Conjecture.

During the talk we shall outline most well known theorems and conjectures of the field, and sketch recent joint results (obtained with A. Raspaud and M. Wo\'zniak) on certain list extensions of the 1--2--3--Conjecture and its total version. These concern sparse graphs with ${\rm Mad}(G)<\frac{5}{2}$ investigated by means of the discharging method combined with the algebraic approach of N. Allon known as \emph{Combinatorial Nullstellensatz}.

Vendredi 28 novembre 2014 (14h) - Degree/Diameter Problem in Host Graphs - Premek Holub.
Résumé : The degree diameter problem involves finding the largest graph (in terms of the number of vertices) subject to constraints on the degree and the diameter of the graph. Beyond the degree constraint there is no restriction on the number of edges (apart from keeping the graph simple) so the resulting graph may be thought of as being embedded in the complete graph. In a generalization of this problem, the graph is considered to be embedded in some connected host graph, in this paper the honeycomb network. We consider embedding the graph in the $k$-dimensional mesh, in the $k$-dimensional honeycomb grid and in the triangular lattice, and provide upper and lower bounds for the optimal graphs. The particular cases of dimensions 2 and 3 are examined in details.

Vendredi 28 novembre 2014 (15h15) - Algorithmes de pré-traitement de graphes - Marthe Bonamy.
Résumé : Étant donné un problème paramétré de graphes (partition des sommets en k stables, ou en une forêt et au plus k sommets, détection d'un ensemble dominant de taille k, etc), on s'intéresse à des algorithmes efficaces (i.e. de complexité polynomiale) pour simplifier une instance de ce problème. "Simplifier" peut avoir plusieurs sens selon le résultat désiré. Intuitivement, si on cherche à k-colorier un graphe G, et que ce graphe G contient un sommet de degré au plus k-1, on sait que ce sommet n'aura pas d'influence sur le résultat et peut donc être enlevé du graphe, sans qu'il y ait perte d'information.

Après avoir identifié un certain nombre de telles règles de simplification, on veut garantir l'efficacité de l'algorithme de pré-traitement correspondant, au moins sur une sous-classe de graphes (par exemple les graphes planaires). Selon le résultat voulu, on peut chercher à montrer que l'algorithme aboutit toujours au graphe vide, ce qui nous assure que la classe de graphes considérée admet toujours une solution (par exemple les graphes planaires pour le problème de 4-coloration). On peut plus généralement chercher à montrer que l'algorithme aboutit toujours à un graphe de taille bornée par une fonction de k, ce qui nous assure que, à k fixé, on peut en temps polynomial décider s'il y a une solution et en trouver une le cas échéant. Ce type de résultat est intéressant en particulier pour des problèmes que l'on sait NP-durs en général.

Ici, on s'intéresse au problème Feedback Vertex Set (combien de sommets doit-on enlever à un graphe pour obtenir une forêt ?) paramétré par la taille de solution (suffit-il d'enlever k sommets ?), dans le cadre des graphes planaires. On présente un algorithme de pré-traitement qui aboutit en temps linéaire à un graphe planaire de taille au plus 13k. Il s'agit d'une collaboration avec Lukasz Kowalik (Université de Varsovie).

Vendredi 5 décembre 2014 - Programmation multi-objectifs avec la méthode du support, en nombres entiers - Mohammed Chebbah.
Résumé : Pour ceux qui pratiquent l'optimisation en mathématique ( Programmation Mathématique ) connaissent le Simplexe avec ses avantages et Inconvénients , d'autres méthodes existent , les méthodes des points intérieurs , mais en face existent aussi d'autres méthodes , pour d'autres écoles QUI peuvent être aussi efficaces : c'est la MÉTHODE du SUPPORT ou la MÉTHODE Adaptée . Nous avons appris à les utiliser et puis à les développer et les appliquer dans beaucoup d'applications : le combinatoire - Optimisation Globale - Optimisation Stochastique - Contrôle optimale - Multi - Objectif.

Vendredi 12 décembre 2014 - Contributions à l'optimisation de requêtes multidimensionnelles - Sofian Maabout. Soutenance HDR.

Lundi 15 décembre 2014 - Graphes et décompositions - Tom Bouvier. Soutenance de thèse.

Vendredi 19 décembre 2014 - Edge-decompositions of graphs with maximum bounded degree - Guillem Perarnau. Exposé spécial CPU/Axe 3.
Résumé : In this talk I will introduce two problems on edge-decompositions of graphs with bounded maximum degree. First, I will present a new approach to acyclic edge colorings of graphs with large girth. Using it, we obtain asymptotically tight results on a conjecture of Alon, Sudakov and Zaks. In the second part I will talk about the problem of partitioning the edges of a graph in different improper color classes with no monochromatic copy of a fixed graph. I will present an iterative embedding argument that allows us to transfer classical results from Extremal Graph Theory to bounded degree graphs. The common denominator of these two topics is the use of the so-called semirandom method. All the presented results are joint work with Cai, Reed and Watts (Part 1) and with Foucaud, Kang, Krivelevich and Reed (Part 2).

Vendredi 16 janvier 2015 - Rook-drawing de graphes planaires - Claire Pennarun.
Résumé : Les graphes planaires peuvent être représentés de différentes façons : sur une grille (régulière ou non), avec des arêtes droites ou brisées, par contact de formes, sous forme de graphes de visibilité... Fáry a montré que tout graphe planaire possède une représentation plane dans laquelle les arêtes sont des segments de droite. Schnyder a ensuite amélioré ce résultat en prouvant qu'un graphe planaire de taille n peut être dessiné sur une grille de taille (n-2) x (n-2). Nous présentons un nouveau type de dessin de graphes que nous appelons le ``rook-drawing". Étant donné un graphe planaire de taille n, un rook-drawing est une représentation plane de ce graphe dont les sommets sont placés sur une grille régulière n x n, où chaque ligne et chaque colonne porte exactement un sommet, et dont les arêtes sont des segments de droite. Nous présentons tout d'abord un algorithme linéaire permettant de dessiner les graphes planaires extérieurs en rook-drawing. Malheureusement, tous les graphes planaires ne peuvent pas être dessinés en rook-drawing. Nous proposons donc un algorithme linéaire, basé sur la théorie des réaliseurs de Schnyder, qui permet de dessiner tout graphe planaire par rook-drawing en autorisant quelques arêtes brisées. Le dessin final comporte au plus n-2 arêtes brisées.

Vendredi 6 février 2015 - Strong edge-coloring of $(3, \Delta)$-bipartite graphs - Julien Bensmail.
Résumé : An edge-coloring of a graph $G$ is strong if its every color class is an induced matching. The strong chromatic index of $G$, denoted $\chi'_s(G)$, is the least number of colors in a strong edge-coloring of $G$. Greedy coloring arguments show that $\chi'_s$ is upper-bounded by roughly $2\Delta^2$, where $\Delta$ denotes the maximum degree of any graph, though this upper bound is not reached in general. A long-standing conjecture of Erd\H{o}s and Ne\v{s}et\v{r}il (1989) states that the right upper bound on the strong chromatic index should actually be roughly $1.25\Delta^2$, which would be tight as confirmed by a particular family of graphs with a lot of small cycles ($C_4$'s and $C_5$'s). Excluding small cycles (\textit{i.e.} with length at most~$5$) in a graph is expected to make its strong chromatic index decrease, as confirmed notably by Mahdian (2000) for $C_4$-free graphs. This observation made Faudree, Gy\'arf\'as, Schelp and Tuza (1990) conjecture that the strong chromatic index of bipartite graphs (which have no $C_3$'s and $C_5$'s) should be upper-bounded by $\Delta^2$. In the continuity of previous results of Steger and Yu (1993) and Nakprasit (2008), we verify this conjecture for bipartite graphs whose one part is of maximum degree at most~$3$. This is a joint work with A. Lagoutte and P. Valicov.

Vendredi 20 février 2015 - Symmetry breaking, resolvability and locating-domination in graphs - Antonio González. Exposé spécial CPU/Axe 3.
Résumé : A resolving set is a subset of the vertices of a graph such that all other vertices are uniquely determined by their distances to those vertices. The only automorphism of the graph fixing a resolving set is the identity. In general, it is possible to find subsets of vertices with this property (of “destroying” all the automorphisms) and with smaller cardinality than all the resolving sets in the graph; these are cases of determining sets. In this talk, we are going to deal with determining sets and resolving sets. When considering these sets in certain families of graphs, many interesting combinatorial objects can arise; for instance, partial geometries and toroidal grids. Further, the relationship between them leads us to study the so called locating-dominating sets and their relationships with other graph structures such as k-dominating sets and matchings.

Vendredi 6 mars 2015 - Sparsity and fast algorithms for combinatorial problems - Jaroslav Nesetril.
Exposé spécial CPU/Axe 3.
Résumé : Combinatorial problems model many important situations from both theoretical and applied computer science. To find bbroad classes of problems which can be effectively solved is of prime importance which leads to several popuar dichotomies. In the lecture we survey the recent actual development from the point of view sparse vs dense dichotomy. (Joint work with P. Ossona de Mendez -Paris and Prague.)

Lundi 9 mars 2015 - On structural and chromatic properties of 1-planar graphs - Tomas Madaras.
Exposé spécial CPU/Axe 3. Exposé en salle 178 lundi 9 mars de 14h à 15h.
Résumé : The planar graphs have been, within decades of graph theory research, well explored yielding numerous results on their structural and chromatic properties. Along with this research, analogue problems were investigated for graphs which generalize - in various directions - the planar graphs. A particularly interesting generalization concerns the graph drawings in the plane which allow at most one crossing per edge, rising to the family of so called 1-planar graphs. These graphs, although introduced in late sixties of 20th century, were studied in a deeper detail only in the last decade. We survey known results on the global and local structure and chromaticity of 1-planar graphs with emphasis on similarities and fundamental differences when comparing with planar graphs, and several future research directions on an analogue of Steinberg conjecture for 1-planar graphs.

Vendredi 27 mars 2015 - Game Distinguishing Number in Graphs - Kahina Meslem.
Résumé : The distinguishing number of a graph G is a symmetry related graph invariant whose study started a decade ago. The distinguishing number D(G) is the least integer d such that G has a d-distinguishing coloring. A d-distinguishing coloring is a coloring c : V(G)-->{1,...,d} invariant only under the trivial automorphism. In this talk, we introduce a game variant of this parameter. The distinguishing game is a game with two players, the Gentle and the Rascal, with antagonist goals. This game is played on a graph G with a set of d colors (with d a positive integer). Alternatively, the two players choose a vertex of G and color it with one of the d colors. The game ends when all the vertices have been colored. Then the Gentle wins if the coloration is d-distinguishing and the Rascal wins otherwise. This game leads to a definition of two new invariants for a graph G. Those invariants are the minimum numbers of colors needed to ensure that the Gentle has a winning strategy.
We will compute those numbers for several classes of graphs, in particular, cycles, hypercubes and some cartesian products of complete graphs.
We also defined a class of graphs, the involutive graphs, for which the game distinguishing number is at most quadratic in the classical distinguishing invariant.

Vendredi 3 avril 2015 - Labyrinth day.
Exposé spécial CPU/Axe 3.
Résumé : Program for the Labyrinth day:
9h 30- 10h 15 Claire Pennarun (Labri) : Dessin de graphes planaires sur une grille (slides in english).
10h 45 - 11h 45 Patrice Ossona de Mendez (EHESS) Coding loopless maps.
14h -15h Sacha Zvonkine (Labri): Do we know more about enumerating meanders ?
15h 30 -16h 30 Jarik Nesetril (Prague) The labyrinth of Discrete Mathematics: a challenge for the XXI century?
Discussion with Robert Cori (Labri) , Pierre Rosenstiehl (EHESS) and the audience.

Vendredi 17 avril 2015 - Graphes expanseurs, codes correcteurs, classiques et quantiques - Gilles Zémor.
Exposé spécial CPU/Axe 3.
Résumé : Les graphes expanseurs connaissent de nombreuses applications: entre autres, ils permettent de construire des bons codes correcteurs d'erreurs, munis d'algorithmes de décodage efficaces. Nous expliquerons cette connexion, et aborderons un travail récent, avec Anthony Leverrier et Jean-Pierre Tillich, consistant à exploiter cette correspondance dans le cadre des codes correcteurs quantiques.

Lundi 20 avril 2015 - Irregular Labelings - Joe Ryan.
Exposé spécial CPU/Axe 3 en salle 178 à 15h30.
Résumé : In 1988, Chartrand et al., posed the problem, "Assign integer labels to the edges of a simply connected graph in such a way that the graph becomes irregular. What is the minimum value of the largest label over all such irregular assignments?" This minimum value of the largest label is known as the irregularity strength s(G) of a graph G. Several papers followed this introduction to the problem but finding s(G) was showing to be difficult. In 2007 Jendrol et al., modified the problem to include labels of vertices as well as edges. This also expanded the field since now the irregularity could be measured not only at the vertices but also at the edges. Many results followed this modification and the Jendrol article has, to date more than 80 citations. In this talk we will cover some of the more interesting aspects of the field and introduce a new variation.

Vendredi 22 mai 2015 - Calculer les distances dans un graphe en temps constant avec des étiquettes de 0.793n bits - Cyril Gavoille.
Résumé : Dans cet exposé je présenterai une structure de données compacte permettant de calculer en temps constant la distance entre n'importe quelle paire de sommets d'un graphe arbitraire à n sommets. Cette structure de données se présente sous forme d'étiquette associée à chacun des sommets, la distance entre les u et v étant décodée à partir d'un calcul impliquant seulement les étiquettes de u et de v. Cet exposé sera l'occasion de vous parler de la Squashed Cube Dimension, du Theorème de Fleishner et d'Hamiltonisme.

Ce travail est en collaboration, entre autre avec un certain Petersen.

Vendredi 29 mai 2015 - A trick for proving that critical graphs are dense - Alexandr V. Kostochka.
Résumé : We discuss an idea introduced in a paper by Montassier, Ossona de Mendez, Raspaud and Zhu. We show how to use this idea to prove that color-critical graphs are not too sparse. In particular, we show how to prove a conjecture of Gallai from 1963 on the number of edges in color-critical graphs with a given number of vertices. We also show applications of the idea to improper 2-colorings of graphs.

Vendredi 19 juin 2015 - Immersions de digraphes 2-réguliers vs. mineurs de graphes (d'après Matt DeVos) - Eric Sopena.
Résumé : J'ai récemment assisté à un exposé de Matt DeVos (basé sur des travaux en collaboration avec Dan Archdeacon, Stefan Hannie et Bojan Mohar) dont le sujet m'a paru suffisamment intéressant et original pour que je tente d'en faire bénéficier les membres du GT graphes...
Un digraphe est 2-régulier si tous ses sommets sont de degré entrant 2 et de degré sortant 2. Il est possible d'associer un tel digraphe D(G) à tout graphe non orienté G plongé dans une surface orientable (nous verrons comment). Les opérations de suppression et contraction d'arête dans G ont alors un équivalent simple dans D(G) en termes de "séparation de sommet" (splitting). Le théorème de Robertson et Seymour -- qui établit que toute famille de graphes close par mineurs est caractérisée par un ensemble fini de mineurs exclus -- trouve une expression similaire dans le cas des digraphes 2-reguliers mais avec un ensemble de configurations exclues de taille bien moindre : une seule dans le cas du plan (contre deux pour les mineurs de graphes, les fameux K_5 et K_{3,3}), 4 pour le plan projectif (contre 35) et peut-être une dizaine (contre plus de 10000, non résolu à ce jour) pour le tore.

Vendredi 26 juin 2015 - Upper and Lower Bounds for Online Routing on Delaunay Triangulations - Nicolas Bonichon.
Résumé : Consider a weighted graph G whose vertices are points in the plane and edges are line segments between pairs of points. The weight of each edge is the Euclidean distance between its two endpoints. A routing algorithm on G has a routing ratio of c if the length of the path produced by the algorithm from any vertex s to any vertex t is at most c|[st]|. The routing algorithm is online if it makes forwarding decisions based on 1) the k-neighborhood in G (for some integer constant k > 0) of the current position of the message and 2) limited information stored in the message header.

We present an online routing algorithm on the Delaunay triangulation with routing ratio less than 5.90. This improves upon the algorithm with best known routing ratio of 15.48. We also show that the routing ratios of any deterministic k-local algorithm is at least 1.70 for the Delaunay triangulation.

Vendredi 3 juillet 2015 - Colorations de packing - Daouya Laïche.
Résumé : Le nombre packing chromatique χb(G) d’un graphe G=(V,E) est le plus petit entier k tel que l’ensemble des sommets V peut être partitionné en k classes disjointes V1,V2,…,Vk, de façon telle que, pour tout i, la distance entre toute paire de sommets de Vi est supérieure à i.
Dans cet exposé, nous présenterons d'abord la packing coloration des couronnes généralisées de chaînes et de cycles. Nous étendrons ensuite cette notion au cas orienté et considérerons la packing coloration des chemins, des cycles, de leurs couronnes généralisées, et des arbres orientés.

Vendredi 10 juillet 2015 - Indice chromatique fort des graphes distances - Maxime Savaro.
Résumé : Le graphe distance généré par un ensemble D d’entiers naturels non nuls est le graphe dont les sommets sont les éléments de ℤ, et pour lequel les sommets s, s′ sont liés par une arête si et seulement si |s−s′|∊D. Une coloration forte des arêtes d’un graphe est une coloration de ses arêtes, telle que toute chaîne de trois arêtes utilise trois couleurs différentes. Le plus petit nombre de couleurs nécessaire pour colorer un graphe G de la sorte est appelé indice chromatique fort de G, et noté χ′s(G).

Dans cet exposé, nous présenterons des méthodes pour étudier l’indice chromatique fort des graphes distances, nous permettant d’établir que 4|D|+1≤χ′s(G)≤3|D|² pour tout D fini, ainsi que de déterminer la valeur de χ′s(G) (ou à défaut des bornes) pour quelques familles de graphes distances.

Vendredi 17 juillet 2015 - Edge-partitioning a graph into paths: beyond the Barat-Thomassen conjecture - Julien Bensmail.
Résumé : The Barat-Thomassen conjecture asserts that, for every fixed tree T with t edges, there is a positive constant c_T such that every c_T-edge-connected graph G with number of edges divisible by t has a partition of its edges into copies of T. This conjecture was mainly verified for T being a tree of small diameter, until Botler, Mota, Oshiro and Wakabayashi recently proved it for T being a path of any length.

We here consider the influence of the minimum degree parameter on these considerations. As a somewhat stronger result, we prove that every 24-edge-connected graph G can be decomposed into copies of any given path, provided the path length divides |E(G)| and the minimum degree of G is large enough. Here 24 should not be optimal, as we expect the same result to hold for 3-edge-connected graphs.

This is an ongoing work with A. Harutyunyan and S. Thomassé.