Accéder aux actualités Evènements des groupes Liste des groupes publics
Liste des événements uniques du groupe GT Graphes et Applications

 2016-07-08 List star edge coloring of sparse graphs 13:30-14:30Salle 178 In 2008, Liu and Deng introduced an edge version of star coloring. They defined a star-edge coloring of a graph \$G\$ as a proper edge coloring such that every \$2\$-colored connected subgraph of \$G\$ is a path of length at most \$3\$. This notion is intermediate between acyclic edge coloring, when every 2-colored subgraph must be only acyclic, and strong edge coloring, when every 2-colored connected subgraph has at most two vertices. For a graph \$G\$, let the list star chromatic index of \$G\$, \$ch_s'(G)\$, be the minimum \$k\$ such that for any \$k\$-uniform list assignment \$L\$ for the set of edges, \$G\$ has a star edge coloring from \$L\$. We proved already many bounds for the list star chromatic index of subcubic sparse graphs. In this talk, we will consider graphs with any maximum degree \$Delta(G)\$. No bound of the list star chromatic index is known for general graphs. In the case of sparse graphs it is possible to find bounds for the the list star chromatic index. We prove that if the maximum average degree of a graph \$G\$ is less than \$frac{7}{3}\$ (resp., \$frac{5}{2}\$,\$frac{8}{3}\$), then \$ch'_s(G)leq 2Delta(G) -1\$ (resp., \$ch'_s(G)leq 2Delta(G)\$, \$ch'_s(G)leq 2Delta(G) +1\$). Joint work with: André Raspaud. Plus d'infos

 2016-07-01 Large regular graphs with given valency and second eigenvalue 14:00-15:00Salle 178 From Alon-Boppana and Serre, we know that for any given integer \$kgeq 3\$ and real number \$lambda<2sqrt{k-1}\$, there are finitely many \$k\$-regular graphs whose second largest eigenvalue is at most \$lambda\$. In this talk, I will discuss the largest number of vertices in such graphs. This is joint work with Hiroshi Nozaki (Aichi Univ. of Education, Japan), Jack Koolen (Univ. of Science and Technology of China) and Jason Vermette (Missouri Baptist Univ., USA). Plus d'infos

 2016-06-24 Packing Coloring of Undirected and Oriented Generalized Theta Graphs 14:00-15:00Salle 178 The packing chromatic number ??(G) of an undirected (resp. oriented) graph G is the smallest integer k such that its set of vertices V (G) can be partitioned into k disjoint subsets V1, . . . , Vk, in such a way that every two distinct vertices in Vi are at distance (resp. directed distance) greater than i in G for every i, 1 ? i ? k. We prove that the packing chromatic number of any undirected generalized theta graph lies between 3 and max{5, n3 + 2}, where n3 = |{i / 1 ? i ? p, ?i = 3}|, and that both these bounds are tight. We then characterize undirected generalized theta graphs with packing chromatic number k for every k ? 3. We also prove that the packing chromatic number of any oriented generalized theta graph lies between 2 and 5 and that both these bounds are tight. Plus d'infos

 2016-06-17 A Distributed Enumeration Algorithm and Applications to All Pairs Shortest Paths, Diameter 14:00-15:00Salle 178 We consider the standard message passing model; we assume the system is fully synchronous: all processes start at the same time and time proceeds in synchronised rounds. In each round each vertex can transmit a different message of size \$O(1)\$ to each of its neighbours. This paper proposes and analyses a distributed enumeration algorithm of vertices of a graph having a distinguished vertex which satisfies that two vertices with consecutive numbers are at distance at most \$3\$. We prove that its time complexity is \$O(n)\$ where \$n\$ is the number of vertices of the graph. Furthermore, the size of each message is \$O(1)\$ thus its bit complexity is also \$O(n).\$ We provide some links between this enumeration and Hamiltonian graphs from which we deduce that this enumeration is optimal in the sense that there does not exist an enumeration which satisfies that two vertices with consecutive numbers are at distance at most \$2\$. We deduce from this enumeration, algorithms which compute all pairs shortest paths and the diameter with a time complexity and a bit complexity equal to \$O(n)\$. (travail en collaboration avec : J.M. Robson et A. Zemmari) Plus d'infos

 2016-06-10 Coloration des arêtes des graphes planaires 14:00-15:00Salle 178 Un grand théorème de la coloration des arêtes des graphes est le théorème de Vizing. Le théorème dit que pour tout graphe G l’indice chromatique \$chi'(G)\$ de G est \$Delta(G) le chi'(G) le Delta(G)+1\$. Pour tout graphe planaire avec \$Delta ge 8\$ Vizing a prouvé que \$chi'(G)(G) = Delta\$ (Class I). Cette égalité a été prouvée aussi pour \$Delta = 7\$ (Sanders & Zhao) et même pour \$Delta = 5\$ pour des graphes sans triangles. Partant des résultats connus \$Delta = 5, g ge 4\$, \$chi'(G)(G) = 5\$ et \$Delta = 4\$, \$g ge 5\$, \$chi'(G)(G) = 4\$ et inspirés des techniques de réductibilité et déchargement du Théorème des 4 couleurs, nous avons travaillé la réductibilité des graphes avec \$Delta = 4\$, \$g ge 4\$, afin d’aborder la conjecture que les graphes avec \$Delta = 4\$ sans triangles sont de Class I. Plus d'infos

 2016-05-13 Rubik's Cube: One rule to solve them all 14:00-15:00Salle 178 Plus d'infos

 2016-04-08 Four ways to introduce strong edge-coloring 14:00-15:00Salle 178 Strong edge-coloring is a proper edge-coloring, where every two edges at distance at most 2 are assigned distinct colors. In the talk, we introduce four different ways to define strong edge-colorings, considering other related types of edge-colorings. We focus our attention to the results regarding subcubic graphs. Plus d'infos

 2016-04-08 New proof of Seymour's theorem 15:00-16:00Salle 178 In 1981 Seymour proved that every bridgeless graph admits a nowhere-zero 6-flow. We will provide a new proof that uses induction. Plus d'infos

 2016-03-18 Homomorphismes localement injectifs sur les tournois 14:00-15:00Salle 178 Cet exposé présente un travail mené à l'université de Victoria (BC, Canada) avec Stephan Bard, Christopher Duffy, Gary MacGillivray et Feiran Yang. Nous étudions les homomorphismes sur les graphes orientés et ajoutons une contrainte supplémentaire d'injectivité locale pour laquelle plusieurs modèles existent. Cet exposé présente plusieurs définitions différentes et cherche à établir pour chacune la classe de complexité du problème d'existence d'un homomorphisme localement injectif vers un tournoi cible donné. Plus d'infos

 2016-03-04 The coloring problem in graphs with structural restrictions 14:00-15:00Salle 178 Graph coloring is an NP-complete problem in general. Even for a fixed k >= 3 and for a fixed graph H that is not a collection of paths, deciding whether a graph with no induced copy of H is k-colorable is NP-hard. Here we consider the case where H is a path on six vertices. Whether 4-coloring graphs with no induced path on six vertices can be decided in polynomial time remains an open question. We answer positively in the restricted setting of bull-free graphs, through structural observations that lead to a polynomial algorithm. This is joint-work with Frédéric Maffray. Plus d'infos

 2016-02-19 Vertex ranking of a graph 14:00-15:00Salle 178 A vertex ranking of a graph G is a coloring of its vertices, so that for every simple path P, the maximum color occurring in it is unique in P. The vertex-ranking chromatic-number of G, \$chi_{vr}(G)\$, is the minimum number of colors for which G has a vertex-ranking. This notion is well documented in the literature, and has some well known practical applications. In this talk we present a relaxation of the vertex ranking notion, a k-vertex ranking. : A k-vertex ranking of a graph G is a coloring of its vertices, so that for every simple path P of length at most k, the maximum color occurring in it is unique in P. Similarly, The k-vertex-ranking chromatic-number of G, \$chi_{vr_k}(G)\$, is the minimum number of colors with which G can be colored. For planar graphs and minor-free graphs, we show a bound of O(logn) on the k-vertex-ranking chromatic number for k constant. We also provide upper and lower bounds of the 2-vertex-ranking chromatic-number for the families of trees and d-degenerate graphs. We compare our bounds to the bounds already found for the case of ordinary vertex ranking. Joint work with Ofer Neiman and Shakhar Smorodinsky. Plus d'infos

 2016-02-12 1-2(-3) conjecture équilibrée 14:00-15:00Salle 178 La 1-2-3 conjecture a été introduite en 2004 par Micha? Karonski, Tomasz ?uczak et Andrew Thomason. Ils y affirment que pour tout graphe sans composante isomorphe à K_2 il existe une pondération des arêtes avec les entiers 1,2,3, telle que les sommes sur chaque sommet des poids des arêtes incidentes forment une coloration propre des sommets. En 2010, Jakub Przyby?o et Mariusz Wozniak conjecturent que si on permet l'attribution des poids aux sommets également, alors pour tout graphe il existe une telle pondération avec les entiers 1,2. Nous présentons une nouvelle variante de ces pondérations, où on exige qu'elles soient équitables, c.-à-d. que chaque poids soit utilisé le même nombre de fois, à une unité près. Nous exposons en particulier quelques résultats obtenus sur les arbres, les graphes bipartis et les graphes complets. Plus d'infos

 2016-02-05 Résultats récents sur les jeux de coloration 14:00-15:00Salle 178 Le jeu de coloration est une version à deux joueurs du problème de coloration de graphes, où un joueur tente d'empêcher l'autre de réussir à colorier proprement le graphe. Nous présentons quelques résultats récents sur ces jeux : des résultats sur les graphes très peu denses (cactus de grandes mailles), des inégalités de type Nordhaus-Gaddum, et, si nous avons le temps, des résultats sur les 'line graphs'. Plus d'infos

 2016-01-29 Courte classification de quelques jeux combinatoires 14:00-15:00Salle 178 Le jeu de Nim est l’un des jeux combinatoires les plus populaires. Il se joue avec n tas de jetons, et à tour de rôle, deux joueurs prennent un nombre quelconque de jetons d’un des tas. Dans la version conventionnelle du jeu, le joueur à prendre le dernier jetons gagne, mais dans la version misère, celui-ci perd. Le jeu de Nim est très important dans la théorie des jeux combinatoires notamment car il introduit les nimbers, ou nombres de Grundy : à chaque position d’un jeu donné on peut lui associer un entier qui code l’ensemble d’options du jeu. Pour comprendre le jeu, il suffit de connaître ses valeurs de Grundy. Ainsi, on peut classer les jeux selon leurs particularités en version normale et en version misère. Notamment, je vais m’intéresser aux jeux de Nim et de Wythoff pour introdurie quelques classes de jeux. Je voudrais ainsi donner une classifications de certains jeux connus et exposer une nouvelle variante du jeu de Wythoff. Plus d'infos

 2016-01-22 Roots of the chromatic polynomial, spanning trees and minors 14:00-15:00Salle 178 The real and complex roots of chromatic polynomials, which we call chromatic roots, have been studied since the 1940s yet it is not well understood how structural properties of graphs affect their chromatic roots. In this talk we survey some results and open problems, and present recent work on the following question: For a minor-closed class of graphs, what is the infimum of the non-trivial real chromatic roots of the graphs in that class? Plus d'infos

 2016-01-15 Coloration aléatoire de graphes peu denses 14:00-15:00Salle 178 D'après le théorème de Brooks, le nombre chromatique d'un graphe est presque toujours inférieur à son degré maximum. En 1998, Reed a montré que cette borne pouvait être affinée de façon à remplacer le degré maximum par la taille d'une clique maximum dans une fraction de la borne. En d'autres termes, on peut toujours économiser un nombre de couleurs proportionnel à l'écart entre le degré maximum et la taille d'une clique maximum. Ici, on s'intéresse à une étape clé de la preuve correspondante ; comment colorer économiquement un graphe dans lequel aucun sommet ne "voit beaucoup d'arêtes" dans son voisinage ? Nous améliorons la méthode probabiliste utilisée dans ce cas, et appliquons notamment le résultat à la coloration forte d'arêtes (coloration d'arêtes telle qu'aucune arête n'est incidente à deux arêtes de même couleur). Erdos et Nesetril ont conjecturé en 1989 que tout graphe de degré maximum D admet une coloration forte d'arêtes avec 1.25 D^2 couleurs, quand la borne supérieure triviale est de 2 D^2. Notre méthode permet d'améliorer significativement la borne existante (Bruhn et Joos, 2015), ainsi que le théorème de Reed. Ces travaux sont le fruit d'une collaboration avec Thomas Perrett (Technical University of Denmark) et Luke Postle (University of Waterloo). Plus d'infos

 2016-01-08 Power domination in triangulations 14:00-15:00Salle 178 La domination de puissance dans les graphes est un problème qui provient de problèmes de surveillance dans les réseaux électriques. Le but de la domination de puissance est de surveiller tous les sommets d'un graphe donné, à l'aide d'un ensemble S de capteurs. On note M l'ensemble des sommets surveillés. La domination de puissance utilise le processus suivant: - On place des sommets dans un ensemble initial S - (domination) les sommets de S et leurs voisins sont ajoutés à M - (propagation) un sommet de M se "propage" vers un voisin si c'est son seul voisin qui n'appartient pas à M. Ce voisin est ajouté à M. L'étape de propagation se répète tant qu'on trouve un sommet à propager. On dit que S est un emph{ensemble de domination de puissance} si M contient tous les sommets du graphe à la fin du processus. Le emph{nombre de domination de puissance} de G, noté \$gamma_P(G)\$, est la taille minimum de S. Le problème de détermination de \$gamma_P(G)\$ pour un graphe donné a été prouvé NP-complet pour les graphes planaires. Un des obstacles à l'étape de propagation dans les graphes est la présence de certains sommets d'articulation. Nous nous intéressons donc naturellement aux triangulations (graphes dans lesquels toutes les faces sont de degré 3) car elles ne contiennent pas de tels sommets. Nous présentons une preuve que \$gamma_P(G) leq dfrac{n-2}{4}\$ si \$G\$ est une triangulation à \$n geq 6\$ sommets. Plus d'infos

 2015-12-04 On dense codes 14:00-15:00Salle 178 We consider the sphere packing problem in arbitrary dimension: what is the maximum fraction d_n of the Euclidean space Rn that can be covered by unit balls with pairwise disjoint interiors? d_n is known for only for some small values of n, and when n grows, we only have lower bounds. A trivial lower bound states that for every n, d_n >= 2^-n. Minkowski and Hlwaka's Theorem (1905) improved this lower bound by a factor 2. Asymptotic improvements of this bound were obtained (from Rogers, 1947 up to Ball, 1992), all of them being of the form d_n >= c n 2^-n where c is a constant. This problem has a natural reformulation in graph theoretic terms as follows: let G denote the graph whose vertices are the points of the Euclidean space and edges are pair of vertices at distance at most 2 one from the other. The independent sets of G are the sphere packings: so, finding a maximum-density sphere packing is the same as finding a maximum-density independent set in this infinite graph. By using graph theoretic arguments only, Krivelevich et al. established that d_n >= 0.01 n 2^-n for sufficiently large n (2004). In a recent breakthrough, Venkatesh introduced the first superlinear improvement: there are infinitely many n such that d_n >= c n log log n 2^-n, where c is a constant. Venkatesh's result is however non-constructive. In this talk, we focus on Bachoc and Moustrou's constructive proof of Venkatesh's lower bound. Plus d'infos

 2015-11-27 Présentation de Maths à Modeler 14:00-15:00Salle 178 Plus d'infos

 2015-11-20 Incidence coloring : Cold Cases 14:00-15:00Salle 178 Incidence coloring has been defined in the 90s as a strong coloring of vertex-edge incidences. In the first part of the talk, connections to other types of colorings will be presented. Then we will present a couple of results, obtained recently in cooperation with M. Macekova, M. Mockovciakova, E. Sopena and R. Sotak, covering som cases that had been left open in the previous works on this topic. Plus d'infos

 2015-11-13 Symmetry Breaking in Graphs 14:00-15:00Salle 178 The distinguishing index D'(G) of a graph G is the least cardinal d such that G has an edge colouring with d colours that is preserved only by the trivial automorphism. This is an analog to the notion of the distinguishing number D(G) of a graph G, which is defined for colourings of vertices by Albertson and Collins. We obtain a general upper bound \$D'(G)leqDelta(G)\$ unless G is a small cycle C_3, C_4 or C_5. We present also quite better bound for some classes of graphs: traceable graphs, claw-free graphs and 3-connected planar graphs.We derive several bounds for infinite graphs, in particular, we prove the general bound \$D'(G)leqDelta(G)\$ for an arbitrary infinite graph. Nonetheless, the distinguishing index is at most two for many countable graphs, also for the Cartesian product of denumarable graphs. In the second part of the talk we introduce the distinguishing chromatic index \$chi'_D(G)\$ defined for proper edge-colourings of a graph G. A correlation with distinguishing vertices by colour walks is shown. We prove that \$chi'_D(G)leqDelta(G)+1\$ except for four small graphs C_4, K_4, C_6 and K_{3,3}. It follows that each connected Class 2 graph G admits a minimal proper edge-colouring, i.e., with \$chi'(G)\$ colours, preserved only by the trivial automorphism. Finally we show that this proper colouring breaking all non-trivial automorphism with \$Delta +1\$ colours could be expanded for infinite graphs. Plus d'infos

 2015-10-23 The N+-Perfect Graph Conjecture for Claw-Free Graphs 14:00-15:00Salle 178 The subject of this talk is the study of the Lovasz-Schrijver PSD- operator N+ applied to the edge relaxation ESTAB(G) of the stable set polytope STAB(G) of a graph. We are particularly interested in the problem of characterizing the graphs G for which N+(G) := N+(ESTAB(G)) equals STAB(G), called N+-perfect graphs, and to find an appropriate polyhedral relaxation of STAB(G) that coincides with N+(G) and STAB(G) if and only if G is N+-perfect. An according conjecture has been recently formulated (N+-Perfect Graph Conjecture); we verify it for the well-studied class of claw-free graphs. Plus d'infos

 2015-10-16 i-Mark: A new subtraction division game 14:00-15:00Salle 178 Given two finite sets of integers S ? N {0} and D ? N {0, 1}, the impartial combinatorial game i-Mark(S, D) is played on a heap of tokens. From a heap of n tokens, each player can move either to a heap of n ? s tokens for some s ? S, or to a heap of n/d tokens for some d ? D if d divides n. Such games can be considered as an integral variant of Mark-type games, introduced by Elwyn Berlekamp and Joe Buhler and studied by Aviezri Fraenkel and Alan Guo, for which it is allowed to move from a heap of n tokens to a heap of ?n/d? tokens for any d ? D. Under normal convention, it is observed that the Sprague-Grundy sequence of the game i-Mark(S, D) is aperiodic for any sets S and D. However, we prove that, in many cases, this sequence is almost periodic and that the set of winning positions is periodic. Moreover, in all these cases, the Sprague-Grundy value of a heap of n tokens can be computed in time O(log n). We also prove that, under misère convention, the outcome sequence of these games is purely periodic. Plus d'infos

 2015-10-09 List star edge coloring of subcubic graphs 14:00-15:00Salle 76 A star edge coloring of a graph G is a proper edge coloring such that every 2-colored connected subgraph of G is a path of length at most 3. For a graph G, let the list star chromatic index of G, ch_s'(G), be the minimum k such that for any k-uniform list assignment L for the set of edges, G has a star edge coloring from L. Dvorak, Mohar and Samal asked whether the list star chromatic index of every subcubic graph is at most 7. We will give a partial answer to this question in this talk by proving that it is at most 8. We will also give some bounds for the list star chromatic index of sparse graphs. Plus d'infos

 2015-10-02 Light structures in sparse graphs with minimum degree 2 14:00-15:00Salle 178 A graph \$H\$ is defined to be light in a graph family \${cal{G}}\$ if there exists finite number \$w(H,{cal{G}})\$ such that each \$G in {cal{G}}\$ which contains \$H\$ as a subgraph, also contains its isomorphic copy \$K\$ with \$sumlimits_{x in V(K)} deg_G(x) leq w(H,{cal{G}})\$. In this talk we will investigate light short paths in families of graphs with bounded average degree and light structures in families of plane graphs of minimum degree 2 with prescribed girth. We will show that every graph with minimum degree at least 2 and average degree \$ad (G) < frac{14}{5}\$ and every plane graph with minimum degree at least 2 and girth \$g(G) geq 7\$ contains a light path on three vertices. Moreover we will give examples providing sharp bounds on \$w(P_3)\$ for families of graphs with prescribed \$ad(G)\$ or \$g(G)\$, respectively. Further we will show that graph \$K_{1,3}\$ is light in the family of plane graphs of girth \$g(G) geq 7\$, with \$delta(G) geq 2\$ and without adjacent 2-vertices, and \$C_{10}\$ is light in family of plane graphs of girth \$g(G)=10\$, with \$delta(G) geq 2\$ and without adjacent 2-vertices. Plus d'infos

 2015-09-18 Homomorphism bounds for K4-minor-free graphs 14:00-15:00Salle 178 A homomorphism of graph G to graph H is a function h from V(G) to V(H) which preserves the edges, i.e. if u,v are adjacent in G, then h(u),h(v) are adjacent in H. Homomorphisms extend the classic notion of proper graph colourings. Given a graph class C, an interesting optimization question is whether there is a graph to which all members of C admit a homomorphism (this graph is called a bound for C). If there exists one, what is the smallest order of such a bound? For example, all planar graphs admit a homomorphism to the graph K4 (this is the Four Colour Theorem), but no smaller graph is a bound. In this talk, we discuss the related problem of determining bounds for planar graphs and their subclasses, with some additional girth restrictions. Our focus will be on K4-minor-free graphs, i.e. series-parallel graphs. This is joint work with Laurent Beaudou and Reza Naserasr. Plus d'infos

 2015-07-17 Edge-partitioning a graph into paths: beyond the Barat-Thomassen conjecture 14:00-15:00Salle 178 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é. Plus d'infos

 2015-07-10 Indice chromatique fort des graphes distances 14:00-15:00Salle 178 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. Plus d'infos

 2015-07-03 Colorations de packing 14:00-15:00Salle 178 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. Plus d'infos

 2015-06-26 Upper and Lower Bounds for Online Routing on Delaunay Triangulations 14:00-15:00Salle 178 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. Plus d'infos

 2015-06-19 Immersions de digraphes 2-réguliers vs. mineurs de graphes (d'après Matt DeVos) 14:00-15:00Salle 76 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. Plus d'infos

 2015-05-29 A trick for proving that critical graphs are dense 14:00-15:00Salle 178 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. Plus d'infos

 2015-05-22 Calculer les distances dans un graphe en temps constant avec des étiquettes de 0.793n bits 14:00-15:00Salle 178 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. Plus d'infos

 2015-04-20 Irregular Labelings 15:30-16:30Salle 178 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. Plus d'infos

 2015-04-17 Graphes expanseurs, codes correcteurs, classiques et quantiques. 14:00-15:00Salle 178 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. Plus d'infos

 2015-03-27 Game Distinguishing Number in Graphs 14:00-15:00Salle 178 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. Plus d'infos

 2015-03-09 On structural and chromatic properties of 1-planar graphs 14:00-15:00Salle 178 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. Plus d'infos

 2015-03-06 Sparsity and fast algorithms for combinatorial problems 14:00-15:00Salle 178 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.) Plus d'infos

 2015-02-20 Symmetry breaking, resolvability and locating-domination in graphs 14:00-15:00Salle 178 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. Plus d'infos

 2015-02-06 Strong edge-coloring of (3, Delta)-bipartite graphs 14:00-15:00Salle 178 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. A long-standing conjecture of Erdos and Nesetril (1989) states that the right upper bound on the strong chromatic index should be roughly 1.25Delta^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 i.e. with length at most 5) in a graph is expected to make its strong chromatic index decrease. This made Faudree, Gyarfas, 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. Plus d'infos

 2015-01-16 Rook-drawing de graphes planaires 14:00-15:00Salle 178 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. Plus d'infos

 2014-12-19 Edge-decompositions of graphs with maximum bounded degree 14:00-15:00Salle 178 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). Plus d'infos

 2014-12-05 Programmation multi-objectifs avec la méthode du support, en nombres entiers 14:00-15:00Salle 178 Plus d'infos

 2014-11-28 Degree/Diameter Problem in Host Graphs 14:00-15:00Salle 178 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. Plus d'infos

 2014-11-28 Algorithmes de pré-traitement de graphes 15:15-16:15Salle 178 É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, etc), on s'intéresse à des algorithmes efficaces (i.e. polynomiaux) pour simplifier une instance de ce problème. 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 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). Plus d'infos

 2014-11-14 Locally irregular graph colourings 14:00-15:00Salle 178 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 o{1,2,ldots,k}\$ with \$sum_{e i u}c(e) eqsum_{e i 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 o{1,2,ldots,k}\$ with \$sum_{e i u}c(e) eqsum_{e i 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. Plus d'infos

 2014-11-07 On Colouring Games 14:00-15:00Salle 178 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. Plus d'infos

 2014-10-10 La méthode des atomes en théorie des graphes et en théorie des nombres 14:00-15:00Salles 178 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. Plus d'infos

 2014-10-03 (f,g)-alliance auto-stabilisante avec convergence sûre 14:00-15:00Salle 178 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. Plus d'infos

 2014-09-19 AVD coloring 14:00-15:00Salle 178 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. Plus d'infos

 2014-07-11 Coloration distribuée et probabiliste 14:00-15:00Salle 178 La coloration est un problème classique de la théorie des graphes et de l'algorithmique distribuée. Dans cet exposé, je ferai un résumé des résultats obtenus récemment pour la résolution de ce problème. On montrera comment obtenir une (Delta+1)-coloration en O(log n) rondes et en utilisant des messages à 1 bit. Nous montrerons que l'algorithme est optimal et ce en utilisant des revêtements de graphes. Dans le cas où le réseau est un anneau, nous verrons qu'en utilisant la transformée de Mellin, il est possible de donner la valeur exacte de la constante cachée dans le O(log n). Plus d'infos

 2014-07-04 Codes séparateurs et surveillance de trafic 14:00-15:00Salle 178 Cette présentation porte sur les problèmes de séparation dont un exemple bien étudié au Labri est celui de code identifiant dans un graphe. Dans le cas général, il s'agit de trouver un ensemble de propriétés aussi petit que possible permettant de distinguer un ensemble d'individus donné. Nous étudierons des modèles basés sur différentes structures combinatoires et comparerons leur expressivité. Nous nous intéresserons ensuite au problème de surveillance de trafic dans un réseau qui consiste à déterminer où placer des capteurs sur les arcs d'un graphe pour pouvoir reconstituer le chemin suivi par un marcheur. Nous exprimerons ce problème comme un problème de séparation en introduisant un nouveau modèle : la séparation sur un langage. Nous étudierons ensuite ce nouveau problème et développerons des algorithmes de résolution, particulièrement sur les instances spécifiques issues du problème de surveillance de trafic. Plus d'infos

 2014-06-20 Incidence coloring of graphs with high maximum average degree 14:00-15:00Salle 178 An incidence of an undirected graph G is a pair (v,e) where v is a vertex of G and e an edge of G incident to v. Two incidences (v,e) and (w,f) are adjacent if one of the following holds: (i) v = w, (ii) e = f or (iii) vw = e or f. An incidence coloring of G assigns a color to each incidence of G in such a way that adjacent incidences get distinct colors. In this talk we present bounds for incidence chromatic number of graphs having high maximum average degree. In particular we prove that every graph with maximum degree at least 7 and with maximum average degree strictly less than 4 admits a (Delta+3)-incidence coloring. This result implies that every triangle free planar graph with maximum degree at least 7 is (Delta+3)-incidence colorable. Plus d'infos

 2014-06-13 Constructing generalized Sudokus 13:30-14:30Salle 178 Mathematical structure behind the world famous Sudoku puzzle is abundant. Using linear algebra and coding theory, it is possible to build Sudokus and special Sudoku squares with additional constraints and symmetries (symmetric Sudokus). We examine these beautiful constructions and use them to generalize the notion of Sudoku to higher dimensional structures. Borrowing ideas from varying areas of mathematics, we define and construct a variant on the hypercube which we call a hyperSudoku. Plus d'infos

 2014-06-06 2-distance coloring of not-so-sparse graphs 14:00-15:00Salle 178 The 2-distance coloring of a graph G is a proper coloring of G where every pair of vertices sharing a common neighbor receives different colors. The "maximum average degree" or "mad" of a graph is the maximum among the average degrees of its subgraphs. This is a way to evaluate the density (or the sparseness) of a graph, both globally and locally. Several results exist about the lesser number of colors needed for 2-distance coloring of graphs with bounded mad. However, in all these results, the bound is strictly less than 4. We present upper and lower bounds for the "2-distance chromatic number" of graphs with mad bounded by 2k for every k. Plus d'infos

 2014-05-23 Hamilton Cycles in Colour Graphs 14:00-15:00Salle 178 We will consider the problem of listing all colourings of a graph so that consecutive colourings in the list differ at exactly one vertex. Plus d'infos

 2014-04-18 Largeur de rang des graphes dénombrables. Définitions et compacité. 14:00-15:00Salle 178 La largeur de rang d'un graphe G, notée rwd(G), (en anglais rank-width) a été introduite par Oum et Seymour dans un but algorithmique, notamment la construction d'algorithmes FPT. On peut souhaiter étendre cette notion aux graphes infinis, et viser la "compacité" : rwd(G) = borne supérieure des rwd(H) pour H sous graphe induit fini de G. La définition la plus naturelle donne "seulement" que la largeur est au plus 2 fois la borne supérieure considérée ci-dessus. En utilisant une notion d'arbre différente (quasi-arbre), qui autorise une infinité de noeuds sur le chemin entre 2 noeuds, on obtient la compacité exacte. Cette notion est définie en logique du premier ordre. On regardera aussi dans cette perspective la largeur de rang linéaire, où l'arbre de décomposition est un ordre total sur les sommets du graphe. Plus d'infos

 2014-04-11 Détection des roues dans les graphes 14:00-15:00Salle 178 Les configurations de Truemper que sont les pyramides, les theta-graphes, les prismes et les roues permettent de définir une famille de graphes les excluant en tant que sous-graphes induits : les "universally signable graphs". Je présenterais lors de ce GT des résultats de complexités sur la détection de ces sous-graphes, et plus précisemment celui sur la détection de la roue. Plus d'infos

 2014-04-04 Tout ce que vous n'avez jamais voulu savoir sur les meilleurs ordres 14:00-15:00Salle 178 De temps en temps, on tombe sur une définition mathématique et on se demande quel est l'esprit pervers qui a bien pu pondre cette « chose ». C'est la réaction que j'ai eue quand j'ai vu la définition de meilleur ordre. Mais comme je dois être un peu pervers moi aussi, j'ai voulu comprendre cette définition. Et comme souvent, en découvrant le contexte et les motivations de cette définition, tout s'éclaire. Dans cet exposé, je présenterai certains résultats liés à la théorie des ordres et pourquoi la notion de meilleur ordre est naturelle. Plus d'infos

 2014-03-28 Graphe couvrant planaire de degré borné 14:00-15:00Salle 178 This talk considers the question: « What is the smallest maximum degree that can be achieved for a plane spanner of a complete Euclidean graph? » Without the planarity constraint, it is known that the answer is 3 which is also the best known lower bound on the degree of any plane spanner. With the planarity requirement, the best known upper bound on the maximum degree is 6, the last in a long sequence of results improving the upper bound. In this talk we show that the complete Euclidean graph always contains a plane spanner of maximum degree 4. Plus d'infos

 2014-03-21 Méthode de compression d'entropie et applications 14:00-15:00Salle 178 Nous essaierons de décrire une méthode générale basée sur la méthode de compression d'entropie permettant d'obtenir de nouveaux majorants sur des invariants de graphes tels que le nombre chromatique acyclique, le nombre de Thue, ... Plus d'infos

 2014-03-14 Variants of edge-colouring 14:00-15:00Salle 178 A strong edge-colouring of a graph is a partition of its edge-set into induced matchings. It is known that planar graphs can be strongly edge-coloured with 4Delta+4 colours, where Delta is the maximum degree of the graph. We improve this bound for several subfamilies of planar graphs and discuss some interesting links to a long standing conjecture of Vizing on proper edge-colouring of planar graphs. In the last part of the talk we will discuss a natural generalization of these two types of colourings where for two adjacent vertices the sets of colours incident to their edges have an intersection of bounded size. This last problem is related to some problems in combinatorial set theory. This is joint work with two groups of authors: J. Bensmail, A. Harutyunyan, H. Hocquard and V. Borozan, N. Cohen, J.C. Chang, N. Narayanan, R. Naserasr. Plus d'infos

 2014-03-07 Planar graphs with minimum cycle length at least 5 are (3,5)-colorable 14:00-15:00Salle 178 A graph is (d_1,...., d_r)-colorable if its vertex set can be partitioned into r sets V_1,......, V_r where the maximum degree of the graph induced by V_i is at most d_i for each i in {1,... r}. Let G_g denote the class of planar graphs with minimum cycle length at least g. We focus on graphs in G_5 since for any d_1 and d_2, Montassier and Ochem constructed graphs in G_4 that are not (d_1, d_2)-colorable. It is known that graphs in G_5 are (2, 6)-colorable and (4, 4)-colorable, but not (3, 1)-colorable. We prove that graphs in G_5 are (3, 5)-colorable, leaving two interesting questions open: (1) are graphs in G_5 also (3, d_2)-colorable for some d_2 in {2, 3, 4}? (2) are graphs in G_5 indeed (d_1, d_2)-colorable for all d_1+d_2=8 where d_2>= d_1 >=1? Plus d'infos

 2014-02-21 Jeu de coloration 14:00-15:00Salle 178 Dans le jeu de coloration sur un graphe G, Alice et Bob colorent proprement, tour à tour, un sommet non coloré de G, construisant ainsi une coloration propre partielle de G de taille croissante. Alice gagne si, avec l'ensemble de couleurs disponibles, elle parvient à terminer la coloration. Bob gagne s'il réussit à rendre la coloration du graphe impossible. Ce problème est étudié depuis un peu plus de 20 ans : dans cet exposé, nous reviendrons sur les principaux résultats, les stratégies les plus efficaces et les plus utilisées, les méthodes de preuve les plus courantes et les conjectures les plus motivantes. Et, peut-être, on présentera quelques résultats. Plus d'infos

 2014-02-14 Une introduction au calcul quantique tolerant aux fautes 14:15-15:15Salle 178 Alors que les composants classiques sont suffisamment fiables, chaque manipulation d'un bit quantique a une probabilité non négligeable d'introduire une erreur. Ceci rend l'application d'une porte quantique délicate. Je présenterai différentes techniques permettant de transformer un circuit quantique en un circuit quantique tolérant aux fautes. Plus d'infos

 2014-02-07 Mise à jour locale de graphes aléatoires 14:00-15:00Salle 178 Les graphes k-sortants sont des graphes orientés dont chaque sommet possède exactement k voisins sortants. Nous étudions le problème de maintenir la distribution uniforme sur ces graphes lors d'une séquence arbitraire d'insertions et de suppressions de sommets. Le but étant de modéliser l'évolution de réseaux logiques dynamiques, nous nous plaçons dans un modèle local où nous n'avons pas accès à l'ensemble des sommets. Nous supposons à la place l'accès à une primitive globale renvoyant un sommet aléatoire uniforme du graphe. Nous présenterons dans cet exposé plusieurs algorithmes d'insertion et de suppression pour le problème de maintenance, dont les plus efficaces sont asymptotiquement optimaux. Plus d'infos

 2014-01-24 Flips 14:00-15:00Salle 178 We review results concerning edge flips in triangulations concentrating mainly on various aspects of the following question: Given two different triangulations of the same size, how many edge flips are necessary and sufficient to transform one triangulation into the other? We focus both on the combinatorial perspective (where only a combinatorial embedding of the graph is specified) and the geometric perspective (where the graph is embedded in the plane, vertices are points and edges are straight-line segments). We highlight some of the techniques used to prove the main results and mention a few of the challenges remaining in this area. Plus d'infos

 2014-01-17 Le jeu de domination est P-Space log-complet 14:00-15:00Salle 178 Dans cet exposé informel, nous (re-)découvrirons le jeu de domination et le paramètre associé, le nombre de domination ludique. Après avoir un peu présenté les avancées récentes sur le jeu, nous vérifierons une réduction du jeu (en espace logarithmique) vers un problème P-Space complet, montrant la complétude du jeu de domination. Il faut noter que, à ma connaissance, il n'existe pas encore de tel résultat pour la version classique du jeu de coloration et du nombre chromatique ludique. Plus d'infos

 2014-01-10 Les configurations d'entiers sur les sommets d'un graphe et leurs rangs 14:00-15:00Salle 178 Dans le modèle du tas de sable (et aussi du "chip firing game") on suppose donné un graphe (non orienté) et une configuration initiale consistant en des jetons attribués à ses sommets. Une règle de transition entre configurations appelée éboulement consiste pour un sommet ayant un nombre de jetons supérieur ou égal à son degré à donner un jeton à chacun de ses voisins. Baker et Norine (2007) ont généralisé ce modèle en supposant que le nombre de jetons attribué à chaque sommet peut être positif ou négatif (dans ce cas le sommet a une dette). Ils généralisent la règle d'éboulement en supprimant la condition d'avoir suffisamment de jetons pour effectuer un éboulement. Une première question consiste à déterminer les configurations qui peuvent aboutir par une suite d'éboulements à une absence de sommets endettés. Ils introduisent aussi une notion plus sophistiquée qui est celle du rang d'une configuration. Après avoir donné des propriétés du rang, on montrera comment le calculer pour certaines familles de graphes. Plus d'infos

 2013-12-20 Sur la L1-réalisabilité des triangulations. 14:00-15:00Salle 76 On dit qu’une triangulation T (carte planaire dont toutes les faces internes sont des triangles) est Delaunay réalisable s’il existe un nuage de points P tel que la triangulation de Delaunay associée à ce nuage de point est égale à T. Dans cet exposé nous nous intéressons à la Delaunay réalisabilité des triangulations pour la norme L1. Nous présenterons des conditions nécessaires puis des conditions suffisantes pour qu’une triangulation soit L1-Delaunay réalisable. Les résultats présentés font intervenir un représentant de la famille des objets comptés par Baxter. Plus d'infos

 2013-12-13 Decomposing oriented graphs into six locally irregular subgraphs 14:00-15:00Salle 178 An undirected graph G is locally irregular if every two of its adjacent vertices have distinct degrees. In case G is not locally irregular but there is a partition (E_1, E_2, ..., E_k) of E(G) such that E_i induces a locally irregular subgraph of G for every i in {1, 2, ..., k}, we say that G is decomposable into k locally irregular subgraphs. It was recently conjectured that every undirected graph should be decomposable into three locally irregular subgraphs, unless it belongs to a well-characterized set of indecomposable graphs. We here consider an oriented version of the same problem, where a locally irregular oriented graph is defined as an oriented graph whose adjacent vertices have distinct outdegrees. Similarly as for the undirected case, we suspect every oriented graph to be decomposable into three locally irregular subgraphs. Towards this conjecture, we prove that every oriented graph is decomposable into six locally irregular subgraphs. This result contrasts with the undirected case for which no such constant upper bound has been proved so far. We finally establish the NP-completeness of the problem of deciding whether an oriented graph is decomposable into two locally irregular subgraphs. This is joint work with Gabriel Renault. Plus d'infos

 2013-11-22 Vertex distinguishing colorings of graphs 14:00-15:00Salle 178 Let us consider a proper coloring f of edges in a simple graph G=(V,E). Such a coloring defines for each vertex \$xin V\$ the palette of colors, i.e., the set of colors of edges incident with x, denoted by S(x). Two vertices x and y are similar if S(x)=S(y). The minimum number of colors required in a proper coloring f without two similar vertices is called the vertex-distinguishing index, and is denoted by vdi(G). The vertex-distinguishing index was introduced and studied (as ``observability'' of a graph) by Cerny, Hornak and Sotak and, independently, (as ``strong coloring") by Burris and Schelp. In general, for some families of graphs, the vertex-distinguishing index can be much greater than the maximum degree. For instance, consider a vertex-distinguishing coloring of a cycle of length n with k colors. Since each palette is of size two, and the number of all possible palettes cannot be smaller than \$n\$, we have \${kchoose 2}ge n \$. Hence, \$vdi(C_n) ge sqrt{2n}\$. However, if we distinguish the vertices in another way, namely by sets of color walks starting from vertices, not just by their palettes, then the number of colors we need is very close to the chromatic index. Some relationships to other `distinguishing' parameters will be discussed such as the distinguishing chromatic index, i.e., the minimum number of colors in a proper edge-coloring preserved only by the identity automorphism. Plus d'infos

 2013-11-22 Maximal cliques in Paley graphs 15:15-16:15Salle 178 For infinitely many primes p = 4k + 1 we give a slightly improved upper bound for the maximal cardinality of a set B subset Z_p such that the difference set B − B contains only quadratic residues. Namely, instead of the ”trivial” bound |B| ≤ sqrt{p} we prove |B| ≤sqrt{p} − 1, under suitable conditions on p. The new bound is valid for approximately three quarters of the primes p = 4k + 1. Joint result with C. Bachoc and I. Z. Ruzsa. Plus d'infos

 2013-11-08 Jeu de domination et graphes no-minus 14:00-15:00Salle 178 Le jeu de domination est un jeu a deux joueurs dont le plateau est un graphe fini sur lequel les joueurs construisent un ensemble dominant. Les joueurs choisissent chacun leur tour un sommet qui domine au moins un nouveau sommet et l’ajoutent a l’ensemble. Le jeu se termine lorsque l’ensemble ainsi construit forme un ensemble dominant. Un des joueurs, Dominator, a pour but d’arriver a un ensemble le plus petit possible, alors que l’autre joueur, Staller, essaie d’en maximiser la taille. Le nombre de domination ludique, noté γ_g , est la taille de cet ensemble lorsque les deux joueurs jouent de façon optimale et que Dominator commence la partie. On note γ'_g le paramètre défini de la même manière en considérant que Staller commence la partie. On s’intéresse ici a une classe de graphes pour laquelle on a toujours γ_g ≤ γ'_g , qu’on appelle les graphes “no-minus”, et dont le comportement vis-à-vis du jeu de domination est plus prévisible que dans le cas général. En particulier, on montre que les graphes “tri-split” et les graphes “dually-chordal” sont des graphes “no-minus”. Plus d'infos

 2013-10-25 Graphes sur des surfaces et codes quantiques 14:00-15:00Salle 76 Les cycles d'un graphe définissent un code correcteur simple et décodable efficacement. Les analogues quantiques d'un code des cycles d'un graphe sont constitués de la donnée simultanée de deux codes des cycles, l'un associé à un graphe dessiné sur une surface, et l'autre associé à son graphe dual. Soumettre un code des cycles à un canal à effacements revient graphiquement à regarder des sous-graphes aléatoires. On ne peut pas décoder si et seulement si le sous-graphe contient un cycle. Dans le cas quantique, l'événement pertinent survient lorsque le sous-graphe contient un cycle non-homogue à zéro. L'étude de ce phénomène permet d'obtenir une formule semi-explicite, permettant d'avoir des bornes supérieures non-triviales, sur la probabilité critique de la percolation sur les pavages réguliers auto-duaux du plan hyperbolique. Travail commun avec Nicolas Delfosse. Plus d'infos

 2013-10-18 Partition Graphs and characterization of designs by graph homomorphims 14:00-15:00Salle 178 Software testing makes use of combinatorial designs called covering arrays. These arrays are a generalization of Latin Squares and orthogonal arrays. Idealy we look to use the smallest possible array for the given parameters, but this is a hard problem. We define a family of graphs, partition graphs, which give a full charatcerization of optimal covering arrays using homomorphisms. These graphs have interesting properties and many interesting open questions. Plus d'infos

 2013-10-04 Polyhedra associated with identifying codes 14:00-15:00Salle 76 The identifying code problem is a newly emerging search problem, challenging both from a theoretical and a computational point of view, even for special graphs like bipartite graphs. Hence, a typical line of attack for this problem is to determine minimum identifying codes of special graphs or to provide bounds for their size. In this work we study the associated polyhedra and present some general results on their combinatorial structure. We demonstrate how the polyhedral approach can be applied to find minimum identifying codes for particular graphs. Also we describe facet defining inequalities for the identifying code polyhedron of some bipartite graphs and odd cycles. Finally, we discuss further lines of research in order to obtain other facet defining inequalities to be added to linear relaxations of the identifying code polyhedron, in order to obtain suitable cutting planes to be used in a B&C framework. Plus d'infos

 2013-09-27 Rayon de propagation 14:00-15:00Salle 178 Au cours de cet exposé, nous présenterons la notion de rayon de propagation introduite récemment pour mesurer l'efficacité d'un ensemble dominant de puissance. Nous présenterons quelques résultats associés sur les graphes de Sierpinski, une famille fractale de graphes. Plus d'infos

 2013-06-28 Clique-Width, Tree-Width and Split Graphs 14:00-15:00Salle 178 Tree-width and clique-width are two usefull graph parameters. Indeed thanks to the well known Courcelle's theorems some problems that are NP-complete in general can be solved in polynomial time when apllied on graph of bounded tree-width or clique-width. What we present here is a strong relation between the tree-width of general graphs and the clique-width of some split graphs. Plus d'infos

 2013-06-14 Orientations "k-faibles" : un résultat de complexité 14:00-15:00Salle 178 Une orientation d'un graphe non orienté G est k-faible si pour toute paire de sommets {u,v} de G il existe un chemin de longueur au plus k reliant u et v dans n'importe quel sens. Durant cet exposé, nous montrerons que déterminer si un graphe non orienté admet une orientation k-faible est un problème NP-complet pour tout k>=2. La NP-complétude du problème où k=2 implique qu'il est NP-complet de déterminer si un graphe non orienté est l'équivalent d'une clique pour la coloration orientée des graphes non orientés, i.e. si son nombre chromatique orienté vaut exactement son ordre. Travail réalisé en collaboration avec R. Duvignau et S. Kirgizov. Plus d'infos

 2013-06-07 Connexion arc en ciel dans les graphes orientés 14:00-15:00Salle 178 Un graphe arête colorié est arc-en-ciel connecté si pour toute paire de sommets u,v, il existe un chemin arc-en-ciel de u à v, c'est-à-dire un chemin n'utilisant pas deux fois la même couleur. Le nombre minimal de couleurs nécessaires pour arc-en-ciel connecter un graphe est le nombre de connectivité arc-en-ciel. Nous établirons des conditions nécessaires et suffisantes pour que le rainbow connection number d'un graphe orienté soit égal à son ordre, et proposerons des bornes pour le rainbow connection number des tournois. Plus d'infos

 2013-05-31 Dicots, and a taxonomic ranking for misère games 14:00-15:00Salle 178 We study combinatorial games in misère version. In a general context, little can be said about misère games. For this reason, several universes were earlier considered for their study, which can be ranked according to their inclusion ordering. We study in particular a special universe of games called dicots, which turns out to be the known universe of lowest rank modulo which equivalence in misère version implies equivalence in normal version. We also prove that modulo the dicot universe, we can define a canonical form as the reduced form of a game that can be obtained by getting rid of dominated options and most reversible options. We finally count the number of dicot equivalence classes of dicot games born by day 3. Plus d'infos

 2013-04-19 Applications of an algorithmic proof of Lovasz Local Lemma 14:00-15:00Salle 178 The Lovasz Local Lemma is a powerful tool to give existential proofs of combinatorial objects with some properties. It says that if some events happen with small probabilities and are not too much dependent of each other, the probability that no event happens is positive. Recently, Moser gave an algorithmic proof of this lemma, based on entropy compression. I will explain the ideas of this very elegant method that leads to constructive and strong results trough two examples : acyclic edge coloring of graphs and non-repetitive words. This is based on joint work with Louis Esperet (G-SCOP, Grenoble, France). Plus d'infos

 2013-04-05 From edge-colouring to strong edge-colouring 14:00-15:00Salle 178 The strong edge-colouring of G is a proper edge-colouring of G such that two edges joined by another edge are coloured with distinct colours. In other words a strong edge-colouring of a graph is a partitioning of its edge set in a set of induced matchings. First we will present several results about strong edge-colouring. In the second part we discuss a natural generalization of both edge- and strong edge-colouring: the k-intersection edge-colouring. It is a proper edge-colouring such that every pair of adjacent vertices u,v share at most k colours. Contrary to the previous two notions, colouring even "simple" classes of graphs does not seem to be an easy task. We will present asymptotically tight upper and lower bounds for the k-intersection chromatic index for these families of graphs. Moreover we show that, not surprisingly, the associated decision problem is NP-complete for different values of k. This is a joint work with different sets of authors from Bordeaux, Montpellier, Orsay, India, Japan and Taiwan. Plus d'infos

 2013-04-05 une version dimensionnelle du théorème de Vosper 15:15-16:15Salle 178 Notre résultat principal est le suivant: dans une extension séparable de degré premier d'un corps k, les paires de k-sous-espaces vectoriels A,B tels que la dimension de l'espace engendré par le produit AB égale dim A + dim B -1, sont, à l'exception de cas dégénérés simples, des translatés multiplicatifs des espaces de polynômes de degrés strictement inférieurs à dim A pour l'un, à dim B pour l'autre, et évalués en un élément z de l'extension. Nous utiliserons la méthode isopérimétrique, ou atomique, d'Hamidoune dont la motivation originelle est l'étude de la connexité dans les graphes mais qui s'est avérée également très utile en combinatoire additive. Travail commun avec Oriol Serra. Plus d'infos

 2013-03-29 The complexity of signed graph homomorphisms. 15:15-16:15Salle 178 Signed graphs are graphs with signed edges (i.e. positive and negative) with an equivalence relation based on a re-signing operation. They have been used, for example, as a way of extending classical results in graph colouring (in relation with graph minors) or in the theory of flows. Recently, the notion of homomorphisms of signed graphs has been introduced by Bertrand Guenin and further developed by Reza Naserasr, Edita Rollova and Eric Sopena. It naturally extends the notion of homomorphisms for classical graphs to the case of signed graphs. We study the computational complexity of the \$H\$-signed colouring problem, i.e. the question of deciding whether a given signed graph admits a homomorphism to a fixed signed graph \$H\$. We settle all cases where \$H\$ is a cycle, and discuss the restriction where the input graph is planar. We relate these questions to the state of the art for classical graph homomorphisms. This is joint work with Reza Naserasr. Plus d'infos

 2013-03-22 Coloration localement irrégulière des arêtes d’un graphe 14:00-15:00Salle 178 Une problématique récurrente de la théorie des graphes est celle de la distinction des sommets voisins au sein d’un graphe. Le principe consiste à colorer les éléments du graphe en respectant un ensemble de contraintes, et ce de sorte que deux de ses sommets voisins soient distinguables grâce à la coloration obtenue. Deux paramètres entrent donc en jeu, à savoir le type de coloration ainsi que les conditions faisant que l’on considère deux sommets comme distingués. Plusieurs variantes du problème ont été étudiées pour des définitions précises de ces deux paramètres. Dans notre version du problème, nous ne colorons que les arêtes du graphe et nous considérons que deux de ses sommets sont distingués s’ils sont de degrés différents dans le sous-graphe induit par la couleur de l’arête les joignant. Une coloration des arêtes permettant de distinguer deux sommets voisins de cette manière est dite localement irrégulière. Tout graphe n’admet pas de coloration localement irrégulière de ses arêtes. En revanche, nous conjecturons que tout graphe colorable (au sens de la coloration d’arêtes localement irrégulière) admet une telle coloration utilisant au plus 3 couleurs. Dans cet exposé, nous montrerons tout d’abord que cette conjecture est vraie pour diverses familles de graphes. Puis, nous prouverons que même si cette conjecture était vraie, le problème de déterminer s’il existe une coloration localement irrégulière des arêtes d’un graphe utilisant au plus 2 couleurs resterait NP-complet en général. Travail réalisé en collaboration avec O. Baudon, J. Przybylo, E. Sopena et M. Wozniak. Plus d'infos

 2013-02-15 3-Colourable Circulant Graphs 14:00-15:00Salle 178 The circulant graph G(n;S) is a graph on vertex set V={v_0,v_1, ...,v_(n-1)} with an edge joining v_i and v_j whenever i =(j + s) mod n for s in {s_1, s_2, ..., s_k}. In this talk, I will present infinite families of circulant graphs for which each graph G(n;S) has chromatic number 3. First, I will present a family of 3-colourable circulant graphs with k chord lengths. Then I will present a family of 3-colourable circulant graphs with 2 chord lengths. I will also show that recursive circulant graphs and a class of optimal double loop graphs are 3-colourable. This is joint work with Nenad Obradovic and Goran Ruzic. Plus d'infos

 2013-02-08 Méthode de compression d'entropie et applications aux problèmes de coloration de graphes 14:00-15:00Salle 178 Nous nous intéresserons à la coloration acyclique des graphes et prouverons via la méthode de compression d'entropie la majoration obtenue par Alon, McDiarmid et Reed sur le famille des graphes de degré maximum borné (la preuve originale est basée sur le lemme local de Lovasz), tout en améliorant la constante multiplicative. Plus d'infos

 2013-02-01 Problèmes de linéarisation/circularisation de graphes et hypergraphes motivés par l'assemblage de génomes 14:00-15:00Salle 178 L'assemblage de génomes à partir de données de séquençage comporte deux phases : le calcul de segments génomiques (contigs), en général non-chevauchants, le calcul de l'organisation (ordre relatif) et de l'orientation de ces contigs le long du ou des chromosome(s). Cette seconde étape, le scaffolding (échafaudage) repose sur la données de lien entre paires ou groupes de contigs et l'approche classique consiste à rechercher une organisation/orientation qui est supportée par le plus grand nombre de liens. Je vais décrire la modélisation de ce problème en termes de graphes et d'hypergraphes, ainsi que des résultats positifs (algorithmes) et négatifs (preuves de NP-complétude) que nous avons récemment obtenus sur ce sujet, ainsi que quelques questions sur lesquelles nous progressons lentement. Travail en collaboration avec Ashok Rajaraman (SFU), Eric Tannier (INRIA Lyon), Murray Patterson (SFU/UBC/Lyon), Jano Manuch (UBC/SFU) et Roland Wittler (Bielefeld). Plus d'infos

 2013-01-25 Realizations in Domination game 14:00-15:00Salle 178 Domination game is a game on a finite graph which includes two players. First player, Dominator, tries to dominate a graph in as few moves as possible; meanwhile the second player, Staller, tries to hold him back and delay the end of the game as long as she can. In each move at least one additional vertex has to be dominated. The number of all moves in the game in which Dominator makes the first move and both players play optimally is called the game domination number and is denoted by \$gamma_g\$. The total number of moves in a Staller-start game is denoted by \$gamma_g'\$. In the talk i will address three different problems regarding realization of game domination number. Plus d'infos

 2012-12-14 Comment avoir précisément 1/2 coup d'avance à un jeu 14:00-15:00Salle 76 Une petite présentation (pour nous) et expérimentation (pour vous) ludique de la représentation des jeux partisans par des nombres surréels, tels que définis par J.H.Conway. Les expérimentations seront proposées sur les jeux de Hackenbush et de Col. Plus d'infos

 2012-12-14 Le nombre thêta de Lovász : applications, généralisations, et problèmes ouverts (2) 15:15-16:15Salle 76 Nous ferons un petit tour d'horizon des applications en théorie des codes et en géométrie euclidienne du nombre thêta de Lovász, une introduction a la hiérarchie de Lasserre des programmes SDP pour le nombre d’indépendance d'un graphe dont thêta est le premier niveau, et nous présenterons quelques questions ouvertes. Plus d'infos

 2012-11-30 Combinatorial properties of fullerene graphs 14:00-15:00Salle 178 Fullerene graphs, i.e.~3-regular planar graphs with faces of size 5 and 6, are used to capture the structure of fullerenes, carbon molecules discovered recently. In this talk we present structural and/or asymptotic results concerning various combinatorial properties of fullerene graphs, such as cyclic edge-connectivity, number of perfect matchings, size of a minimum maximal matching, and cost of bipartisation. Plus d'infos

 2012-11-09 Computational complexity of partitioning a graph into a few connected subgraphs 14:00-15:00Salle 178 Let G be a graph. A sequence τ = (n'_1_', ... , n'_k_') of positive integers summing up to |V(G)| is realizable in G if there exists a partition (V'_1_', ..., V'_k_') of V(G) such that each V'_i_' induces a connected subgraph of G on n'_i_' vertices. Deciding whether τ is realizable in G was proven to be a NP-complete problem in general, even when τ contains only one integer value or G is a tree with maximum degree 3. In this talk, we will show that this problem remains NP-complete even when τ has only 2 elements. This result involves that there is no constant threshold on the size of τ under which the problem above becomes easy. Additionally, we will introduce some other graph partition problems and locate them in the second level of the polynomial hierarchy. Plus d'infos

 2012-10-19 Le jeu de Timber 14:00-15:00Amphi du LaBRI Nous proposons une variante impartiale du jeu Toppling dominoes, Timber. Le jeu se joue sur un graphe orienté. Deux joueurs choisissent à tour de rôle un arc du graphe. Lorsqu'un arc (x,y) est choisi, il est retiré du jeu ainsi que la composante connexe contenant y dans le graphe non-orienté sous-jacent (ne contenant plus l'arête (x,y)). En version normale, le premier joueur ne pouvant jouer (car il n'y a plus d'arc) perd la partie. En version misère, ce même joueur gagne la partie. Un graphe est perdant (pour le premier joueur) si le second joueur dispose d'une stratégie gagnante. Nous caractérisons les graphes connexes perdants en version normale, et les chemins perdants en version misère. Nous remarquons par ailleurs que le nombre de chemins perdants de longueur paire en version normale est donné par les nombres de Catalan. Plus d'infos

 2012-10-12 La fonction theta de Lovasz est-elle unique? 14:00-15:00Salle 76 La fonction theta est la "seule" fonction réelle connue calculable en temps polynomial, permettant de déterminer le nombre chromatique des graphes parfaits. Elle s'exprime sous la forme d'un programme d'optimisation sur l'ensemble convexe des matrices semi-définies positives. Dans cet exposé, j'apporterai quelques éléments d'explication de son "unicité" en considérant un ensemble de fonctions définies par le même programme d'optimisation mais sur des ensembles convexes de matrices plus grands que celui des matrices SDP. Plus d'infos

 2012-10-05 Algorithmes de graphes polynomiaux utilisant des automates (infinis) à compteurs 14:00-15:00Salle 178 Le titre est explicite. Les propriétés envisagées ne sont pas exprimables en logique du second-ordre monadique: Exemples: régularité, partition d'un graphe en p sous-graphes réguliers, p-coloriage "équilibré". L'objectif est néanmoins d'obtenir des "méta-théorèmes" algorithmiques. Plus d'infos

 2012-09-28 omplete oriented colourings and the oriented achromatic number 14:00-15:00Salle 178 A complete k-colouring of an undirected graph G is a proper k-colouring of the vertices of G such that, for every pair of colours {a,b}, there is an edge in G whose endponts are coloured with a and b. The achromatic number of G is then the largest k for which G admits a complete k-colouring. In this talk, we will study complete colourings of oriented graphs and the associated new notion of the oriented achromatic number. Plus d'infos

 2012-09-21 The Stretch Factor of \$L_1\$- and \$L_infty\$-Delaunay Triangulations 14:00-15:00Salle 178 In this talk I will show that the stretch factor of \$L_1\$-Delaunay and \$L_infty\$-Delaunay triangulations is equal to \$sqrt{4+2sqrt{2}} approx 2.61\$. Between any two points \$x,y\$ of such triangulations, we construct a path whose length is no more than \$sqrt{4+2sqrt{2}}\$ times the Euclidean distance between \$x\$ and \$y\$, and this bound is the best possible. This definitively improves the 25-year old bound of \$sqrt{10}\$ by Chew (SoCG '86). This work presented at ESA'12 is in collaboration with N. Bonichon, N. Hanusse and L. Perkovic. Plus d'infos

 2012-09-14 Domination de puissance dans les graphes réguliers 14:00-15:00Salle ALP, batiment A9 Power domination in graphs was birthed from the problem of monitoring an electric power system by placing as few measurement devices in the system as possible. A set of vertices is defined to be a power dominating set of a graph if every vertex and every edge in the system is monitored by the set following a set of rules (according to Kirschoff laws) for power system monitoring. Last year, we proposed some common generalization to domination and power domination. Whereas the definition of a power dominating set implies some propagating behavior of the set of monitored vertices, a phenomenon very different from the standard domination parameter, this generalization revealed some common properties of the two problems. After a rather general introduction on power domination and its generalization, we will show some recent bounds on the generalized power domination number of regular graphs. Plus d'infos

 2012-06-22 Partitioning Harary graphs into connected subgraphs containing prescribed vertices 14:00-15:00Salle 178 A graph G is said to be arbitrarily partitionable (AP for short) if for every partition (tau_1, ..., tau_p) of |V(G)| there exists a partition (V_1, ..., V_p) of V(G) such that each V_i induces a connected subgraph of G with order tau_i. If, additionally, each of k of these subgraphs contains an arbitrary vertex of G prescribed beforehand, then G is said to be AP+k. Complete graphs on strictly more than k vertices are AP+k but are not convenient because of their size. In this talk, for any k ≠ 2 and n ≥ k+1, we will see that the Harary graph H_{k+1,n}, known to be one of the smallest (k+1)-connected graphs on n vertices, is AP+k. To overcome the fact that H_{3,n} is not AP+2 for some n, we will also introduce a class of edge-minimal 3-connected AP+2 graphs to complete our hierarchy of AP+k graphs with minimum size. These results are best possible in the sense that we cannot allow more prescriptions while partitioning these graphs. Joint work with O. Baudon, J. Przybyło, E. Sopena, and M. Woźniak. Plus d'infos

 2012-06-15 Application de la théorie spectrale des graphes à des objets musicaux. Modélisation et visualisation en Hyperespace 14:00-15:00Amphi du LaBRI Nous déduisions puis projetons spectralement le produit cartésien C3 □ C4, afin de construire le "graphe Planet", solution unique répondant aux conditions de symétrie propres à l'espace des notes de musique de notre système tempéré. Nous utilisons une coloration à deux dimensions pour les sommets, ainsi que la technique de projection spectrale pour créer un modèle géométrique dont les sommets sont en surface d'une hypersphére. Celle-ci se décline ensuite selon les applications et contextes musicaux. La projection spectrale est aussi utilisée pour comparer différents "Pitch Spaces" (répartitions spatiales de notes) ou claviers d'instruments. Dans le cas de réseaux d'accords non circulants, nous utilisons des "graphes de graphes" circulants et symétriques afin d'obtenir des visualisations simples. Plus d'infos

 2012-05-15 Chemins disjoints avec congestion dans les graphes à mineur exclu 11:00-12:00Amphi du LaBRI Nous étudions le problème de trouver un nombre maximum de chemins disjoints dans des classes de graphes fermées par mineur. En général, ce problème est très difficile à approximer, même dans des classes très simples comme les graphes planaires, avec des ratios d'inapproximabilité en \$Omega(sqrt{n})\$ ou plus. Pour contourner cette difficulté, plusieurs travaux autorisent l'utilisation de congestion: sous congestion \$c\$, on autorise \$c\$ chemins à utiliser la même arête. Chuzhoy a montré en 2011 qu'en permettant une congestion constante, il existe une algorithme de ratio polylogarithmique. Si nous cherchons plutôt des algorithmes ayant des ratios d'approximations constants, Chekuri, Khanna et Shepherd ont pu trouver un algorithme avec ratio d'approximation constant et congestion 2, dans le cas des graphes planaires. Nous souhaitons généraliser ce résultat, et nous prouvons que pour les graphes à largeur d'arbre bornée, et pour les graphes plongeables dans une surface fixée, il existe des algorithmes avec ratio et congestion constants. Ces deux types de classes de graphes étant fermées par mineur, nous conjecturons que toute classe de graphes à mineur exclu admet de tels algorithmes. Plus d'infos

 2012-05-11 Complexity and algorithms for max-coloring problems 14:00-15:00Salle 178 We deal with generalizations of the classical graph edge/vertex-coloring problems motivated by scheduling questions arising in computer and communication systems. The most general problems we attack are called bounded max-edge/vertex-coloring problems and take as input an edge/vertex weighted graph and a bound b. In these problems each color class is of cardinality at most b and of weight equal to that of the heaviest edge/vertex in this class. The objective is to find a proper coloring of the input graph minimizing the sum of all color classes' weights. For unit weights these problems reduce to the known bounded coloring problems, while in the absence of the cardinality bound we get the (unbounded) max-coloring problems. The max-coloring problems have been well motivated and studied in the literature. Max-edge-coloring problems arise in switch based communication systems, like SS/TDMA, where messages are to be transmitted through direct connections established by an underlying network. Max-vertex-coloring problems arise in the management of dedicated memories, organized as buffer pools, which is the case for wireless protocol stacks like GPRS or 3G. Moreover, max-coloring problems correspond to scheduling jobs with conflicts in multiprocessor or batch scheduling environments. However, in all practical applications there exist physical constraints on the number of entities (corresponding to vertices/edges of a graph) assigned the same resource (color), which motivate the study of the bounded max-coloring problems. In this talk, we present complexity results as well as algorithms for the bounded max-edge/vertex-coloring problems. Plus d'infos

 2012-05-04 Perfect matchings in cubic graphs 14:00-15:00Salle 178 Lovász and Plummer conjectured in the 1970's that cubic bridgeless graphs have exponentially many perfect matchings. This conjecture has been verified for bipartite cubic graphs by Voorhoeve in 1979, and for planar cubic graphs by Chudnovsky and Seymour in 2008. Then several general lower bounds for the number of perfect matchings in cubic bridgeless graphs appeared, and finally, the conjecture has been settled last year. In this talk, a survey on methods used to attain these results is provided. Plus d'infos

 2012-04-27 Méthode d'accélération en optimisation global 14:00-15:00Salle 178 Depuis quelques années, les algorithmes de branch and bound ont montré leur intérêt pour la résolution exacte de problèmes d'optimisation non-convexes avec contraintes. Cependant, ces méthodes nécessitent parfois beaucoup de temps CPU, c’est pourquoi l’intégration de méthode d’accélération s’avère généralement indispensable. Nous reviendrons sur différentes techniques basées sur l'analyse d'intervalles, des algorithmes de réduction de boites issue de la programmation par contraintes, ainsi que des techniques de calcul de borne basées sur des relaxations linéaires et SDP. Plus d'infos

 2012-04-13 Arbitrarily Partionable Graphs 14:00-15:00Salle 178 Soit G un graphe d'ordre n et n1, ..., nk une suite d'entiers dont la somme vaut n. G est dit (n1, ..., nk)-partitionable s'il est possible de partitionner ses sommets en une suite de k sous-ensembles disjoints V1, ..., Vk telle que pour tout i, |Vi| = ni et le sous-graphe induit par Vi est connexe. Un graphe est dit arbitrairement partitionnable s'il est (n1, ..., nk)-partitionable pour toute suite d'entiers (n1, ..., nk) dont la somme vaut n. Nous présenterons quelques résultats récents sur ce problème, en particulier sur des questions de degré maximum, et de taille des composantes lorsque l'on enlève un séparateur. Plus d'infos

 2012-04-06 Une (nouvelle?) décomposition canonique des graphes fortement connexes. Applications aux mots de Gauss 14:00-15:00Salle 178 We introduce a canonical decomposition of strongly connected graphs that we call the *atomic decomposition*. We can construct it in linear time from the canonical decomposition in 3-connected components (by Tutte) of the considered graph. With it, we study *Gauss words*: these words are associated with self-intersecting closed curves in the plane.We characterize, up to homeomorphism, all such curves with a given Gauss word. We extend this characterization to tuples of words, associated with tuples of closed curves in the plane. Plus d'infos

 2012-03-23 Des codes (correcteurs) systématiques représentés sur une grille 14:00-15:00Amphi E, bât A29 Un code à correction d'erreurs est l'espace des mots utilises dans les communications digitaux (téléphone, satellites, CD) pour encoder les messages qu'on veut transmettre. Un bon code est un ensemble de mots qui permet au décodeur de reconstituer le message envoyé même s'il y a eu du "bruit" pendant la transmission. La quantité de bruit que l'on peut corriger dépend du code choisi et elle est reliée a la distance entre les mots. On présente une classification des codes systématiques basée sur la distance a l'aide de la résolution d'un système polynomiale multivarié. Cela est en générale assez difficile a résoudre, mais si on visualise ces codes sur une grille (les sommets sont les codes de différents paramètres et les arêtes sont des inclusions) pas seulement on peut simplifier les calcules du système, mais aussi on trouve des propriétés de structure. Plus d'infos

 2012-02-24 Des limites de la coloration quasi propre 14:00-15:00Salle 178 Une coloration quasi propre est une coloration des sommets où chaque classe de couleurs induit un sous graphe de degré maximum fixé. Dans cet exposé, nous nous intéresserons au cas où les couleurs sont de deux types: a couleurs induisant un sous graphe de degré maximum d, et b couleurs induisant un stable (coloration propre): on parle de (d,a,b)*-coloration. Nous montrons que tout graphe dont le mad (degré moyen maximum) est inférieur à une certaine fonction f est (d,a,b)*-coloriable. Cette fonction f tend (par valeurs inférieures) vers 2a+b quand d tend vers l'infini. Ce résultat est asymptotiquement optimal : il existe des graphes non (d,a,b)*-coloriables dont le mad tend (par valeurs inférieures également) vers 2a+b. Ceci montre en quelque sorte qu'en terme de degré moyen, une couleur d-impropre n'est pas plus efficace que deux couleurs propres. Plus d'infos

 2012-02-17 Induced decomposition of graphs 14:00-15:00Salle 178 Given two graphs F and G, an induced F-decomposition of G is a partition of E(G) into induced copies of F. Bondy and Szwarcfiter defined the value ex(n; F) as the maximum number of edges of a graph of order n admitting an induced F-decomposition and studied its values for several families of graphs F. In this talk, I will present an explanation of the asymptotic behaviour of the function "ex", by showing that ex(n, F) = (1/2) n^2 - o(n^2). This result has been obtained in collaboration with Zsolt Tuza. Plus d'infos

 2012-02-10 Petite histoire d'une petite preuve. 14:00-15:00Salle 178 Grötschel, Lovasz et Schrijver ont démontré en 1984 que le nombre Theta de Lovasz d'un graphe minimal imparfait n'est pas entier. Pour les besoins d'une preuve d'un lemme, j'ai réutilisé cet argument pour un graphe partitionable bien spécifique, en mentionnant que le résultat ci-dessus s'appliquait en fait à tous les graphes partitionables. Voici la réponse sur ce point d'un arbitre d'humeur taquine: "I would advise to give a proof, along the lines of the reference - it is not difficult and it is informative to have the argument in the paper." Puisque cette preuve est "informative" et "not difficult", je vous en expliquerai le mécanisme dans cet exposé, puis vous montrerai comment faire "mieux" dans le cas qui m'intéressait. Plus d'infos

 2012-02-03 Quelques problèmes classiques sur des graphes dynamiques 14:00-15:00Salle 178 Nous présenterons un modèle de graphes dynamiques et la transposition de problèmes classiques (plus court chemins, flots...) sur ces graphes. Nous présenterons aussi le problème des corrélations dans l'évolution, qui est intrinsèquement lié à la dynamique du modèle. Plus d'infos

 2012-01-20 Paired versus double domination in graphs 14:00-15:00Salle 178 A vertex is said to dominate itself and its neighbours. A subset of vertices in a graph is a dominating set if it dominates all the vertices. It is a paired dominating set it induces a perfect matching. A dominating set is a double-dominating set if it dominates every vertex twice. In this talk, we will discuss relationship between these two parameters, and especially in the case when the graph does not contain induced stars of a given order. Plus d'infos

 2012-01-13 Strong chromatic index of planar graphs with large girth 14:00-15:00Salle 178 Let \$G\$ be a graph. A {em strong \$k\$-edge-coloring} of \$G\$ is a mapping from \$E(G)\$ to \${1,ldots,k}\$ such that every two adjacent edges or two edges adjacent to a same edge receive two distinct colors. We will give the sketch of the proof of the existence of a linear function \$c(Delta)\$ such that every planar graph with maximum degree \$Delta\$ and girth at least \$c(Delta)\$ is strong \$(2Delta-1)\$-edge colorable, that is best possible (in terms of number of colors) as soon as G contains two adjacent vertices of degree \$Delta\$. Plus d'infos

 2011-12-09 Le théorème du sommet redondant pour les graphes sur les surfaces 14:00-15:00Salle 4, Bât A29 Étant donnés k couples (s1, t1), ..., (sk, tk) de sommets dans un graphes, le problème des k chemins disjoint (k-DDP) demande s'il existe k chemins disjoints dont les extrémités sont les couples (si, ti). Robertson et Seymour ont donné un algorithme qui fonctionne en temps O(n^3) pour résoudre ce problème. Dans certains cas, l'algorithme donne une réponse directe, sinon, il identifie un ''sommet redondant'' dont la suppression ne change pas la réponse au problème. Malheureusement, cet algorithme fait intervenir des constantes dont l'existence n'est montré que de façon existentielle et même si Robertson et Seymour ont affirmé qu'il était possible de rendre effectif leurs preuves, ce travail n'avait pas encore été fini. Dans cet exposé, je présenterai un travail en collaboration avec Geelen, Huynh et Richter dans lequel nous terminons ce travail en donnant une preuve effective du théorème du sommet redondant pour les graphes sur les surfaces. Plus d'infos

 2011-12-02 Bounded-Distance Network Creation Games 14:00-15:00Salle 178 A network creation game simulates a decentralized and non-cooperative building of a communication network. Informally, there are n players sitting on the network nodes, which attempt to establish a reciprocal communication by activating, incurring a certain cost, any of their incident links. The goal of each player is to have all the other nodes as close as possible in the resulting network, while buying as few links as possible. According to this intuition, any model of the game must then appropriately address a balance between these two conflicting objectives. Motivated by the fact that a player might have a strong requirement about its centrality in the network, in this paper we introduce a new setting in which if a player maintains its (either maximum or average) distance to the other nodes within a given associated bound, then its cost is simply equal to the number of activated edges, otherwise its cost is unbounded. We study the problem of understanding the structure of associated pure Nash equilibria of the resulting games, that we call MaxBD and SumBD, respectively. Plus d'infos

 2011-11-04 On acyclic vertex colourings of graphs 15:15-16:15Salle 178 Let P1 , . . . , Pk be hereditary properties. A k-colouring of a graph G is called a (P1 , . . . , Pk )-colouring of G if for 1 ≤ i ≤ k the subgraph induced in G by the colour class Vi (the set of vertices coloured with i) belongs to Pi. Such a colouring is called an acyclic (P1 , . . . , Pk )-colouring if for every two distinct colours i and j the subgraph formed by the edges whose endpoints have colours i and j is acyclic. An acyclic (P1 , . . . , Pk )-colouring is an acyclic k-colouring if for 1 ≤ i ≤ k the property Pi is the set of all edgeless graphs. An acyclic (P1 , . . . , Pk )-colouring such that for 1 ≤ i ≤ k the property Pi is the set of of graphs with degree at most d is called d-improper acyclic colouring. We deal with the acyclic (P1 , . . . , Pk )-colouring where the property Pi (i = 1, . . . , k) is the set of acyclic graphs or the set of graphs with bounded maximum degree. We study the acyclic (P1 , . . . , Pk)-colouring of graphs with bounded degree. Plus d'infos

 2011-11-04 Rainbow numbers and rainbow connection 14:00-15:00Salle 178 In this talk we consider edge colourings of graphs. A subgraph H of a graph G is called rainbow subgraph, if all its edges are coloured distinct. In the first part we will survey the computation of rainbow numbers. For given graphs G,H the rainbow number rb(G,H) is the smallest number m of colours such that if we colour the edges of G with at least m different colours, then there is always a totally multicoloured or rainbow copy of H. For various graph classes of H we will list the known rainbow numbers if G is the complete graph and report about recent progress on the computation of rainbow numbers. Finally, new results on the rainbow numbers rb(Qn,Qk) for the hypercube Qn will be presented. An edge-coloured graph G is called rainbow connected if any two vertices are connected by a path whose edges have distinct colours. This concept of rainbow connection in graphs was introduced by Chartrand et al.. The rainbow connection number of a connected graph G, denoted rc(G), is the smallest number of colours that are needed in order to make G rainbow connected. In the second part we will show several complexity results and present lower and upper bounds for rc(G). We will discuss rc(G) for graphs with given minimum degree. Finally, we will present some recent Erdös-Gallai type results for rc(G). Plus d'infos

 2011-10-28 Degré Minmax et Cycles Interdits 14:00-14:30Salle 178 Plus d'infos

 2011-10-28 Énumération et élection dans les environnements de diffusion multisauts anonymes 14:30-15:00Salle 178 Nous étudions les problèmes de l'énumération et de l'élection dans des environnements de diffusion multisauts. Nous considérons un modèle de communication asynchrone dans lequel chaque noeud du réseau diffuse un message et son voisinage le reçoit après un délai de temps arbitraire inconnu. Ce délai dépend du temps pris par les couches réseaux pour assurer l'acheminement du message. Dans ce travail, nous présentons les conditions nécessaires que doivent satisfaire les graphes pour résoudre ces problèmes puis nous montrons que ces conditions sont suffisantes en fournissant un algorithme pour l'énumération et un algorithme pour l'élection. Pour ces deux problèmes, nous mettons en avant l'importance de la connaissance initiale. Concernant le problème de l'énumération, chaque noeud connait le nombre de noeuds du graphe et, contrairement aux travaux existants, n'a pas connaissance de son voisinage. Pour le problème de l'élection, nous montrons que cette connaissance n'est pas suffisante. Nous proposons un algorithme dans lequel nous supposons que chaque noeud connait une carte du graphe (sans connaitre sa position dans ce graphe). Nos algorithmes offrent une meilleure complexité (mémoire et messages) en regard des travaux existants la réduisant ainsi d'exponentielle à polynomiale. Plus d'infos

 2011-10-21 Partition arbitraire et préaffectation de sommets 14:00-14:30Salle 178 Soit G = (V, E) un graphe d'ordre n. Une partition tau = (tau_1, ..., tau_k) de n, avec tau_1 >= ... >= tau_k, est dite réalisable dans G s'il est possible de partitionner V en k parts V_1, ..., V_k de sorte que quelque soit i de [1,k], le sous-graphe G[V_i] soit connexe et d'ordre tau_i. G est dit arbitrairement partitionnable si toute partition de n y est ainsi réalisable. Plusieurs versions de la partition arbitraire, augmentées de contraintes supplémentaires, ont fait l'objet de diverses études, articulées principalement autour de la famille des arbres. Après un bref rappel des résultats principaux la concernant, nous nous concentrerons sur le cas des graphes biconnexes. Pour cela, nous introduirons une version forte de la partition arbitraire, dite "avec une préaffectation", caractérisant le fait qu'il soit toujours possible de trouver, étant donnés un sommet arbitraire v de G et un entier quelconque i appartenant à [1,k], une réalisation V_1, ..., V_k de tau dans G vérifiant v inclus dans V_i. Une fois la biconnexité des graphes arbitrairement partitionnables de cette manière mise en évidence, nous montrerons qu'il en existe une infinité et étudierons plus spécifiquement certaines classes de graphes, notamment celle des ballons. Plus d'infos

 2011-10-21 Vertex Nim : une variante de Nim dans les graphes 14:30-15:00Salle 178 Le jeu de Nim a été introduit et résolu par Bouton en 1904. En 2003, Fukuyama a proposé une variante de ce jeu qui se joue dans les graphes, avec des poids sur les arêtes. Nous proposons une autre variante, Vertex Nim, qui se joue également dans les graphes, mais avec des poids sur les sommets. Plus d'infos

 2011-09-16 Vizing conjecture or Krop's Theorem 14:00-15:00Amphithéatre du LaBRI Dans un papier récemment placé sur ArXiv (06/09/11), Elliot Krop propose une preuve courte et élégante de la conjecture de Vizing. Cette conjecture, ouverte depuis 1963, dit que le nombre de domination du produit Cartésien de deux graphes est au moins le produit des nombre de domination des facteurs. Nous présenterons cette preuve et l'illustrerons sur un exemple. Plus d'infos

 2011-09-09 Adjacent vertex-distinguishing edge-coloring of graphs 14:00-15:00Salle 178 Plus d'infos

 2011-07-01 The 2-distance coloring of the Cartesian product of cycles using optimal Lee codes. 14:00-15:00Salle 178 Let Cm be the cycle of length m. We denote the Cartesian product of n copies of Cm by G(n, m) := Cm x Cm x · · · x Cm . The k-distance chromatic number χk (G) of a graph G is χ(Gk ) where Gk is the kth power of the graph G = (V, E) in which two distinct vertices are adjacent in Gk if and only if their distance in G is at most k. The k-distance chromatic number of G(n, m) is related to optimal codes over the ring of integers modulo m with minimum Lee distance k + 1. In this paper, we consider χ2 (G(n, m)) for n = 3 and m ≥ 3. In particular, we compute exact values of χ2 (G(3, m)) for 3 ≤ m ≤ 8 and m = 4k, and upper bounds for m = 3k or m = 5k, for any positive integer k. We also show that the maximal size of a code in Z3 with minimum Lee distance 3 is 26. Plus d'infos

 2011-06-24 Minmax Degree of Graphs 14:00-15:00salle 178 The minmax degree of a graph G is the largest integer m such that every edge of G is incident with a vertex with degree at least m. For some classes of graphs, bounds on minmax degree have some consequences on edge-decomposition and game coloring number. During this talk, we shall present some results and perspectives on minmax degree. Plus d'infos

 2011-06-10 Computational Social Choice: Kemeny Scores and Parameterized Complexity 14:00-15:00Amphi du LaBRI The multidisciplinary Consensus Problem: how independent agents reach a joint, collective decision, has applications in political resolution, but also important applications in Health (agreement on services), Image Processing (pixel value), Networks (agreement among processors), Auctions (agreement on bids), Search Engines (agreement on pages), among many others. The objects of study: opinions, rankings, observations, votes, gene sequences, sensor-networks in security systems or climate models, together with the presence of massive datasets, partial or uncertain information, distributed or interoperating decision makers, possibly over various time-frames, with the ability to share information at unprecedented speeds, make the Consensus Problem extremely complex. Plus d'infos

 2011-06-09 Discussion sur les principaux thèmes de recherche dans le domaine des graphes, de leur structuration, de l'algorithmique correspondante 11:00-12:00Salle 178 Plus d'infos

 2011-05-27 2-dipath and oriented L(2,1)-labelings of some families of oriented planar graphs 14:00-15:00Salle 178 To distinguish close and very close transmitters in a wireless communication system, Griggs and Yeh proposed a variation of the Frequency Assignment Problem (or simply FAP) by introducing the notion of L(2,1) labeling. A feature of this graph theoretic models for FAP was that, communication was assumed to be possible in both directions (duplex) between two radio transmitters and, therefore, these models were based on undirected graphs. But in reality, to model FAP on directed or oriented graphs could be interesting, was pointed by Aardal et al in their survey. There are two different L(2,1) labelings of oriented graphs, namely, 2-dipath L(2,1) labeling (that is, a vertex labeling with non negative integers, such that, the label difference for adjacent vertices is at least 2 and for vertices at directed distance 2 is at least 1) and oriented L(2,1) labeling (that is, a 2-dipath L(2,1) labeling which is also an oriented coloring). In this talk, we have improved the existing bounds for 2-dipath and oriented L(2,1) span (the minimum possible "largest" value used for the respective labelings) for the class of planar graphs with girth 5, 11, 16, outerplanar, cactus, wheels and leaf independent Halin graphs. Plus d'infos

 2011-05-20 Nowhere-zero flows in Cartesian bundles of graphs 14:00-15:00Salle 178 A nowhere-zero k-flow on a graph G is an assignment of a direction and a non-zero integer in absolute value smaller than k to each edge of G in such a way that, for each vertex, the sum of incoming values equals the sum of outgoing values. Our work continues and extends the study of nowhere-zero flows on product graphs initiated by Imrich and Skrekovski in 2003. hey proved that the Cartesian product of any two nontrivial connected graphs has a nowhere-zero 4-flow. Product graphs have been examined for many different graph properties because of their relatively simple structure and considerable generality. We have examined a natural (although lesser known) generalisation of the Cartesian product called Cartesian bundle. By combining of flow methods with algebraic methods we will show that every Cartesian bundle of two graphs without isolated vertices has a nowhere-zero 4-flow. This is a joint work with Martin Skoviera. Plus d'infos

 2011-05-13 Rappels sur la méthode probabiliste en théorie des graphes 14:00-15:00Salle 178 La méthode probabiliste est un outil fréquemment utilisé en théorie des graphes, qui permet parfois d'obtenir des résultats élégants avec des preuves simples. Au cours de cet exposé, je vous rappellerai les principes de ce qu'on appelle la méthode probabiliste, illustrés par une série d'exemples dans différents domaines de la théorie des graphes. Les résultats présentés peuvent être retrouvés dans les livres de référence du domaine. Plus d'infos

 2011-04-29 Bounding the identifying code number of a graph using its degree parameters, a probabilistic approach 14:00-15:00Salle 178 An identifying code is a subset of vertices of a graph such that each vertex is uniquely determined by its neighbourhood within the identifying code. Let M(G) denote the minimum size of an identifying code in G. It was conjectured recently that if G is connected, has n vertices and maximum degree d, M(G) <= n-n/d+O(1). In a first part, we use Lovász' Local Lemma to give new upper bounds on M(G) for various classes of graphs in order to get closer to the conjectured bound than already known results. In a second part, we use the first moment method to give improved bounds for graphs having given minimum degree and girth 5. Moreover we show that these bounds are asymptotically tight by computing the identifying code number of random d-regular graphs w.h.p. using the pairing model. This is joint work with Guillem Perarnau (UPC, Barcelona). Plus d'infos

 2011-04-15 Sur la difficulté de séparer un graphe par des plus courts chemins 14:00-15:00Salle 178 Les schémas de routage et de calcul de distances les plus efficaces sont conçus à partir de décompositions hiéarchiques de la topologie en plus courts chemins. Ces constructions sont calculables efficacement pour de nombreuses topologies, comme les graphes planaires par exemple. Dans cet exposé je montrerais cependant que la décomposition d'une topologie arbitraire en k plus courts chemins est NP-difficile. Plus d'infos

 2011-04-08 Nowhere-zero flows on signed eulerian graphs 14:00-15:00Salle 178 A signed graph is a graph in which every edge is labelled with a sign, + or -. In the talk we introduce flows on signed graphs as a natural analogue of flows on unsigned (that is, all-positive) graphs, based on the use of bidirected rather than directed edges. After giving a brief survey of known results about nowhere-zero flows on signed graphs we concentrate on flows on signed eulerian graphs. We show that every signed eulerian graph that has a nowhere-zero flow has a nowhere-zero 4-flow. This indicates a significant difference from the unsigned case where every eulerian graph is known to have a nowhere-zero 2-flow. We also characterise those signed eulerian graphs whose flow number equals 2, 3, and 4, respectively. This is a joint work with Edita Macajova. Plus d'infos

 2011-04-01 Décomposition de graphes 14:00-15:00Salle 178 A graph G is called improperly (d1, ... dk )-colorable, or just (d1, ... dk )-colorable, if the vertex set of G can be partitioned into subsets V1, ... Vk such that the graph G[Vi] induced by the vertices of Vi has maximum degree at most di for all 1 ≤ i ≤ k. This notion generalizes those of proper k-coloring (when d1 = ... = dk = 0) and d-improper k-coloring (when d1 = ... = dk = d ≥ 1). Proper and d-improper colorings have been widely studied. As shown by Appel and Haken, every planar graph is 4-colorable, i.e. (0, 0, 0, 0)-colorable. Eaton and Hull and independently Skrekovski proved that every planar graph is 2-improperly 3-colorable (in fact, 2-improper choosable), i.e. (2,2,2)-colorable. This latter result was extended by Havet and Sereni to not necessarily planar sparse graphs as follows: Theorem. For every k ≥ 0, every graph G with mad(G) < (4k+4)/(k+2) is k-improperly 2-colorable (in fact k-improperly 2-choosable), i.e. (k,k)-colorable. We recall that mad(G) = {max(2|E(H)|/|V(H)|),H ⊆ G}, is the maximum average degree of a graph G. In this talk we will present obtained results concerning the (k, j)-colorability for some values of k and j (k = j) for graphs with a given maximum average degree. Plus d'infos

 2011-03-18 Coloration d'arêtes à distance 2 14:00-15:00Salle 178 Une k-coloration d'arêtes à distance 2 (ou forte) d'un graphe est une coloration d'arêtes telle que deux arêtes adjacentes ou adjacentes à une même arête reçoivent des couleurs différentes. L'indice chromatique fort d'un graphe G est le nombre minimum de couleurs k tel que G admet une k-coloration forte d'arêtes. Dans cet exposé, la première partie sera consacrée à la majoration de l'indice chromatique fort pour certaines classes de graphes et dans la seconde partie nous présenterons des résultats de complexité (du problème de k-coloration forte d'arêtes) pour les graphes planaires. Ce travail a été réalisé en collaboration avec Pascal Ochem et Petru Valicov. Plus d'infos

 2011-03-11 Le "disjoint path problem" et le "minor containement problem". 14:00-15:00Salle 178 Je présenterai un algorithme polynomial pour résoudre ces deux problèmes. Plus d'infos

 2011-03-04 An algorithmic decomposition of claw-free graphs leading to an O (n^3)-algorithm for the weighted stable set problem 14:00-15:00Salle 178 We propose an algorithm for solving the maximum weighted stable set problem on claw-free graphs that runs in \$O(n^3)\$-time, drastically improving the previous best known complexity bound. This algorithm is based on a novel decomposition theorem for claw-free graphs, which is also introduced in the present paper. Despite being weaker than the well-known structure result for claw-free graphs given by Chudnovsky and Seymour, our decomposition theorem is, on the other hand, algorithmic, i.e. it is coupled with an \$O(n^3)-\$time procedure that actually produces the decomposition. We also believe that our algorithmic decomposition result is interesting on its own and might be also useful to solve other kind of problems on claw-free graphs. Plus d'infos

 2011-02-18 Testing Planarity of Partially Embedded Graphs 14:00-15:00Salle 178 We pose and study the following question: Given a (planar) graph G and a planar embedding of its subgraph H, can this be extended to a noncrossing embedding of the entire graph G? This approach follows the paradigm of completing a partial solution of a particular problem, which has been studied in many different situations before. Unlike in many cases, when the presence of a partial solution in the input makes an otherwise easy problem hard, we show that the planarity question remains polynomial-time solvable. Our algorithm is based on several combinatorial lemmas which show that planarity of partially embedded graphs performs the "oncas" behaviour - obvious necessary conditions for planarity are also sufficient. In particular, a 2-connected graph allows an extension of an embedding of its subgraph H if and only the skeleton of each node of its SPQR-tree has an embedding compatible with the given embedding of H. This implies that no dynamic programming is needed for a decision algorithm, the nodes of the SPQR-tree can be processed independently in parallel. It should be noted that though 2-connected graphs form the core situation, nontrivial steps are needed to handle the less connected cases. By refining the techniques and using appropriately adjusted data structures we manage to achieve a linear time algorithm. On the other hand we consider several generalizations of the problem, e.g. minimizing the number of edges of the partial embedding that need to be rerouted, and argue that they already become NP-hard. Plus d'infos

 2011-02-11 Vertex partitions of graphs 14:00-15:00Salle 178 Dans cet exposé, nous parlerons de partition des sommets d'un graphe où le graphe induit par chaque ensemble de la partition est une forêt d'étoiles ou un cographe et répondrons à une question de Gimbel et Nesetril sur le sujet. Ce travail est réalisé en commun avec Paul Dorbec et Pascal Ochem (LRI). Plus d'infos

 2011-02-04 Graphes de très grande maille fondés sur les octonions 14:00-15:00Grand amphi IMB La maille d'un graphe est définie comme la plus petite taille d'un cycle dans ce dernier. Une vieille question en théorie des graphes consiste à étudier quelle est la plus grande maille possible pour un graphe \$d\$-régulier (c'est à dire un graphe où chaque sommet comporte \$d\$ arêtes) et à proposer des familles de graphe atteignant la borne. La meilleure borne supérieure sur la maille est de l'ordre de \$(2+o(1)) log_{d-1} n\$ quand le nombre de sommets \$n\$ tend vers l'infini. De nombreuses constructions atteignant une maille de taille logarithmique en le nombre de sommets ont été proposées par le passé. La construction la plus célèbre est sans nul doute une construction arithmétique fondée sur les propriétés de factorisation des quaternions due à Margulis, Lubotzky, Philips et Sarnak datant de la deuxième partie des années 1980. De manière remarquable, cette construction a aussi fourni la première famille infinie de graphes \$d\$-réguliers qui soit de Ramanujan (c'est une propriété remarquable portant sur le spectre du graphe). La maille de cette famille est de l'ordre de \$4/3 log_{d-1}n\$ et c'était jusqu'à présent la meilleure construction connue pour la propriété de maille. Nous nous inspirons de cette construction fondée sur les quaternions pour proposer une nouvelle construction à base d'octonions dont la maille est de l'ordre de \$12/7 log_{d-1} n\$ nous rapprochant ainsi un peu plus de la borne supérieure susmentionnée. Nous montrons aussi, comme dans le cas de la construction à base de quaternions, que cette nouvelle famille est aussi de Ramanujan par un argument de comptage du nombre de solutions d'une certaine équation diophantienne quadratique. Plus d'infos

 2011-01-21 Rainbow matchings: existence and counting 14:00-15:00Salle 178 Given an edge coloring of a graph, a rainbow matching is a matching where all the edges have different color. In particular we focus on the case when the graph is the complete bipartite graph K(n,n). This problem is analogous to find a latin transversal in integer matrices. A result from Erdos and Spencer (1988) states that if no color appears more than n/4e times then the coloring admits a rainbow matching. In this talk we will show some existence and enumeration results subject to these type of constraints. The Lovasz Local Lemma will be used as a main tool in the sense of Poisson Paradigm. Random models of colorings will be introduced and discussed. Plus d'infos

 2010-12-10 Codes identifants, systèmes de contrôle et graphes sans-jumeaux. 14:00-15:00Salle 178 Un code identifiant dans un graphe est un ensemble dominant C tel que tous les sommets du graphe soient dominés par un ensemble d'éléments de C qui leur soit propre. Nous présenterons cette notion, ainsi que les variantes à distance r fixée et les codes identifiant les ensembles de sommets. On fera un panorama des recherches concernant ces codes : bornes, algorithmes, complexité, ainsi que des graphes sans-jumeaux, intrinsèquement liés aux codes identifiants. Enfin, nous introduirons la notion de système de contrôle, variante des codes identifiants possédant quelques propriétés intéressantes. Plus d'infos

 2010-12-03 Largeur arborescente et dualité sur les surfaces 14:00-15:00Salle 178 Dans Graph Minor 3, Robertson et Seymour on écrit:"It seems that the tree-width of a planar graph and the tree-width of its geometric dual are approximately equal — indeed, we have convinced ourselves that they differ by at most one." Dans cet exposé, je présenterai une preuve d'une généralisation de cet "exercice" laissé au lecteur en genre supérieur et je montrerai que ce résultat est optimal. Plus d'infos

 2010-11-26 Sur la dimension cubique de quelques classes d'arbres 14:00-15:00Salle 76 Résumé : Arffati, Papadimitriou et Papageorgiou ont montré que le problème de décider si un graphe G est plongeable dans un hypercube de dimension donnée est NP-complet. Corneil et Wagner ont montré que ce problème reste NP-complet même dans le cas où G est un arbre. Plusieurs auteurs se sont intéressés à l’étude de plongement d’arbres dans l’hypercube ce qui a permis de caractériser certaines classes. Tous les arbres sont plongeables dans l’hypercube, le problème consiste à donner la plus petite dimension d’un hypercube dans lequel un arbre donné est plongeable. On parle alors d’hypercube optimal et de la dimension cubique de l’arbre. De nombreux problèmes (booléens, de théorie des graphes, de codes…) sont formalisables comme problèmes combinatoires sur l’hypercube, donc il est fondamental de déterminer quels sont les graphes et particulièrement les arbres qui sont plongeables dans l’hypercube et de déterminer aussi combien de copies d’un arbre donné on peut placer (de façon disjointe) dans un hypercube de dimension donnée. Nous avons introduit quelques classes d’arbres pour lesquelles nous avons déterminé la dimension cubique et nous avons aussi donné pour certaines classes le nombre maximum de copies que l’on peut placer dans un hypercube de dimension donnée. Un problème d’une autre nature a été traité, il concerne la détermination du nombre de sommets minimum et du nombre de sommets maximum d’une famille de graphes plongeables dans un même hypercube optimal. Mots-clés : Hypercube, Plongement, Graphe, Arbre, Isomorphisme. Plus d'infos

 2010-10-22 Une étude du jeu de Col 14:00-15:00Salle 178 COL est un jeu combinatoire partisan de coloration de graphes inventé par Colin Vout. En attribuant des valeurs aux instances, on déterminera des stratégies gagnantes sur certaines classes de graphes : les cographes et certaines sous-classes d'arbres. Plus d'infos

 2010-10-15 Vertex distinguishing labelings of graphs 14:00-15:00Salle 178 Let G be a simple connected graph of order n ≥ 3, and let us label each edge of G with a positive integer. As a result we obtain a vertex colouring, where the colour of a vertex is defined by the sum of the numbers on its incident edges. Suppose we use only integers 1,2,...,k as labels. How large must k be for a given graph G ? A striking conjecture of Karonski,Luczak and Thomason asserts that the numbers 1, 2, 3 are sufficient for every graph. We shall discuss best known results in pursuit of the proof of this conjecture, as well as a number of related problems. Among others, we will focus on the “total” counterpart of this conjecture (where also vertices obtain their own initial labels), and the problem where all the vertices, not only the neighbouring ones, are required to have distinct colours (i.e., sums). The later introduces a well known graph invariant called irregularity strength of a graph. Plus d'infos

 2010-10-01 Surveillance de réseaux éléctriques, Power Domination 14:00-15:00Salle 178 Power domination was introduced by Haynes et al as a graph theoretical description of a physical problem. The initial problem, proposed by Baldwin et al was to monitor an electrical network by placing as few phase measurement units as possible. A phase measurement unit placed on a vertex of a graph permits to monitor all the vertices of its closed neighborhood. Then, thanks to Kirschoff laws, any monitored vertex adjacent to only one unmonitored vertex allows to also monitor this neighbour. With these rules, a power dominating set is a set of vertices that allows to monitor the whole graph. The power domination number is the minimum cardinality of a power dominating set. This definition of the problem induces some propagation phenomenon that is uncommon in domination problems, and looks more like the behaviour of some life game. For exemple, the power domination of a path is only one, however long the path is. During this talk, we shall present a common generalization of domination and power domination, denoted k-power domination. In this variant, a monitored vertex adjacent to at most k unmonitored neighbours allows to have these neighbours monitored. When k=1, this is the power domination, and usual domination corresponds to the case when k=0. Surprisingly, studying this new variant, we managed to extend some classical domination results to k-power domination, like for exemple a linear algorithm for trees very different from the algorithm proposed by Haynes et al. We also extended various results of power domination to k-power domination. Plus d'infos

 2010-09-17 Problèmes ouverts de coloration et NP-completude 14:00-15:00Salle 76 Une conjecture bien connue dit notamment que les graphes planaires de maille 8 ont un homomorphisme vers le cycle de taille 5. On montre que si la conjecture est fausse, alors decider si un graphe planaire de maille 8 admet un homomorphisme vers le cycle de taille 5 est un problèmes NP-complet. On donnera aussi des résultats du même genre pour d'autres problèmes ouverts de coloration. Plus d'infos

 2010-09-10 Improved approximability and non-approximability results for graph diameter decreasing problems 14:00-15:00Salle 178 We study two variants of the problem of adding edges to a graph so as to reduce the resulting diameter. More precisely, given a graph G = (V, E), and two positive integers D and B, the Minimum-Cardinality Bounded-Diameter Edge Addition (MCBD) problem is to find a minimum cardinality set F of edges to be added to G in such a way that the diameter of G+F is less than or equal to D, while the Bounded-Cardinality Minimum-Diameter Edge Addition (BCMD) problem is to find a set F of B edges to be added to G in such a way that the diameter of G + F is minimized. Both problems are well known to be NP-hard, as well as approximable within O(log n log D) and 4 (up to an additive term of 2), respectively. In this paper, we improve these long-standing approximation ratios to O(log n) and to 2 (up to an additive term of 2), respectively. As a consequence, we close, in an asymptotic sense, the gap on the approximability of the MCBD problem, which was known to be not approximable within c log n, for some constant c > 0, unless P = NP. Remarkably, as we further show in the paper, our approximation ratio remains asymptotically tight even if we allow for a solution 5 whose diameter is optimal up to a multiplicative factor approaching 3. On the other hand, on the positive side, we show that at most twice of the minimal number of additional edges suffices to get at most twice of the required diameter. Plus d'infos

 2010-06-25 Autour du théorème de caractérisation des graphes sans mineur H 14:00-15:00Salle 178 Au cours de cet exposé, je tenterai de donner quelques idées de la preuve du théorème de Robertson et Seymour qui caractérise les graphes sans mineur H. Plus d'infos

 2010-06-18 Posets, dependent arcs, and colorings 14:00-15:00Salle 178 An arc is dependent in an acyclic orientation if its reversal concretes a directed cycle. In the talk, we will introduce some studies among posets, dependent arcs, and colorings. Plus d'infos

 2010-06-08 A linear time algorithm for L(2,1)-labeling of trees 10:00-11:00Salle 5, Batiment A29 An \$L(2,1)\$-labeling of a graph \$G\$ is an assignment \$f\$ from the vertex set \$V(G)\$ to the set of nonnegative integers such that \$|f(x)-f(y)|ge 2\$ if \$x\$ and \$y\$ are adjacent and \$|f(x)-f(y)|ge 1\$ if \$x\$ and \$y\$ are at distance 2, for all \$x\$ and \$y\$ in \$V(G)\$. A \$k\$-\$L(2,1)\$-labeling is an \$L(2,1)\$-labeling \$f:V(G) ightarrow{0,ldots ,k}\$, and the \$L(2,1)\$-labeling problem asks the minimum \$k\$, which we denote by \$lambda(G)\$, among all possible assignments. It is known that this problem is NP-hard even for graphs of treewidth 2, and tree is one of very few classes for which the problem is polynomially solvable. The running time of the best known algorithm for trees had been \$O(Delta^{4.5} n)\$ for more than a decade, and an \$mO(min{n^{1.75},Delta^{1.5}n})\$-time algorithm has appeared recently, where \$Delta\$ is the maximum degree of \$T\$ and \$n=|V(T)|\$, however, it has been open if it is solvable in linear time. This is a joint work with Toshimasa Ishii, Toru Hasunuma and Yushi Uno. Plus d'infos

 2010-06-04 On packing of graphs, digraphs and hypergraphs 15:00-16:00salle 178 A packing of two graphs G_1 and G_2 into H is a couple of edge disjoint embeddings of G_1 and G_2 into H. We recall first results of packing simple graphs into a complete graph with particular emphasis on packing of multiple copies. Next we observe that in the case of oriented graphs we have significant differences between packing two digraphs and embedding one of them into a complement second. We consider packing into a transitive tournament. At the end we see some results in the topic of packing of hypergraphs. Plus d'infos

 2010-05-28 The doubly-critical graph conjecture 14:00-15:00Salle 178 A graph is said to be doubly-critical if the removal of any two adjacent vertices causes the chromatic number to drop by two. A special case of a long-standing conjecture of Erdos and Lovasz asserts that the only connected doubly-critical graphs are the complete graphs. In this talk, I will survey the known results and discuss some questions related to this conjecture. Plus d'infos

 2010-05-07 Bin Packing avec Contrainte de Distance 14:00-15:00salle 178 Le Bin Packing est un problème NP-Complet classique: étant donné un ensemble d'éléments pondérés, on cherche à minimiser le nombre de groupes de poids borné (identique pour tous les groupes) nécessaires pour que chaque élément appartienne à un groupe. Nous ajoutons une contrainte supplémentaire à ce problème en considérant que les éléments à empaqueter sont placés dans un espace métrique. Deux éléments d'un même groupe ne doivent alors pas être à plus d'une certaine distance dmax préalablement fixée. Nous avons recours à de l'augmentation de ressources pour étudier ce problème: nous autorisons nos algorithmes à construire des groupes de diamètre b*dmax, et comparant le nombre de groupes créés à une solution optimale contrainte à construire des groupes de diamètre dmax. Cette augmentation de ressources est nécessaire puisque nous prouvons que pour tout e>0, il n'existe pas d'algorithme d'approximation à facteur constant pour le bin packing avec distance contrainte utilisant une augmentation de ressource de (2-e). Nous prouvons également que quelque soit l'augmentation de ressource qu'on veut utiliser, il n'existe pas d'algorithme approchant à un facteur inférieur à 3/2 la solution optimale contrainte à dmax. Nous présenterons ensuite un algorithme utilisant une augmentation de ressource de 2, et produisant un facteur d'approximation de 7/3. Enfin nous présentons une équivalence entre le bin packing avec contrainte de distance et le problème du k-centre avec capacité, un autre problème NP-Complet classique. Nos résultats sur le bin packing avec contrainte de distance implique les premiers résultats connus sur la variante non uniforme du k-centre avec capacité. Plus d'infos

 2010-04-23 Chemin séparabilité 14:00-15:00salle 178 Résumé : Il a été montré que les graphes planaires pondérés admettent un séparateur composé de 3 plus courts chemins. Savoir si 2 plus courts chemins sont suffisants pour séparer ces graphes est une question ouverte. Dans cet exposé, je présenterais une famille des graphes planaires qui sont 2-chemins séparables, les face-séparables. Je définirais aussi des familles de graphes k-chemins séparables closes par mineurs. Plus d'infos

 2010-04-16 Extremal cardinalities of identifying codes 14:00-15:00Salle 178 Identifying codes are dominating sets with the property that any two vertices of the graph have distinct neighbourhoods within the identifying code. As a consequence, they can be used to uniquely identify or locate the vertices of a graph. Identifying codes have found many applications, such as for fault diagnosis in multiprocessor networks or the placement of emergency sensors in facilities, and have been widely studied since the introduction of the concept by Karpovski et al. in 1998. In this talk, we present some results on extremal cardinalities of identifying codes. The first part will consist of the characterization of the class of graphs on n vertices having very large minimum identifying codes (i.e. of size n or n-1). In a second part, we present some upper bounds on the minimum cardinality of an identifying code depending on parameters such as the minimum and maximum degree, or the girth of the graph. Plus d'infos

 2010-04-09 NP-complétude pour les colorations impropre, orientée et acyclique 14:00-15:00Salle 178 Résumé : Trois problèmes : * Partition des sommets du graphe sont partitionnables en un stable et un graphe de degré au plus 1 : NP-complet pour les graphes planaires de degré max 3 de maille 7. Réduction à partir de PLANAR-(3,<=4)-SAT. * Homomorphisme d'un graphe orienté vers T4 (le tournoi à 4 sommets contenant un circuit hamiltonien) : NP-complet pour les graphes bipartis planaires de degré max 3 et de maille au moins k (pour tout k fixé). Réduction à partir de PLANAR-(3,<=4)-SAT. * Coloration acyclique en 4 couleurs : NP-complet pour les graphes bipartis planaires de degré max 8. Réduction à partir de PLANAR-3-COLORABILITY. Les réductions de np-complétude sont souvent techniques et soporifiques, mais pas celles-la. Cela se voudra pédagogique et je pourrais sacrifier une des trois preuves si le temps manque. Plus d'infos

 2010-04-02 Problems from the cold 14:00-15:00Salle 178 Résumé : As a new post-doc student in ANR IDEA, I would be glad to present two problems I've been studying during my stay in Montreal this winter. Broadcast in networks: the problem consists in finding an optimal protocol to collect in one specific node, information of the whole networks. The constraint is that each node cannot send more than one unit of information at a time. We provide a polynomial algorithm and discuss about some esthetics. Absorbing sets in arc-coloured tournament: this problem, attributed to Erdös, deals with absorbing sets in arc-coloured tournaments. A set S of vertices is said absorbing if any vertex out of S admits a monochromatic chain to some vertex of S. Can the size of a minimum absorbing set be bounded above by a function of the number of colours? We will present some known result and state open questions. Plus d'infos

 2010-03-26 The hidden matching-structure of the composition of strips 14:00-15:00Salle 178 Composition of strips was introduced by Chudnovsky and Seymour as a key tool for decomposing claw-free graphs. In this talk we are going to reveal the close connection between the stable set problem in composed graphs and the matching theory. We will basically show that anything we can do for the strips, we can extend to composition of strips i.e. polytime algorithm (resp. separation, polyhedral description) for the strip extends to polytime algorithm (resp. separation, polyhedral description) for the composed graph. We will then apply those general results back to where they originated from: stable set in claw-free graphs, to show that the stable set polytope can be reduced to understanding the polytope in very basic structures (for most of which it is already known). In particular for a general claw-free graph \$G\$, we show an integral extended formulation for \$STAB(G)\$ and a procedure to separate in polynomial time over \$STAB(G)\$; moreover, we provide a complete characterization of \$STAB(G)\$ when \$G\$ is any claw-free graph with stability number at least 4 having neither homogeneous pairs nor 1-joins. Plus d'infos

 2010-03-12 Interval graphs and packing problem 14:00-15:00Salle 178 The Bi-dimensional Orthogonal Packing Problem (OPP-2) is a classical NP-complete problem consisting in deciding whether a set of rectangular boxes (items) can be packed in a ”big” rectangular container without overlapping. In the classical formulation of the problem, the rotation of items is not allowed. I will present a new algorithm for solving OPP-2 based on the characterization of solutions using interval graphs proposed by Fekete and Schepers. The algorithm uses MPQ-trees - combinatorial structures introduced by Korte and Möhring for interval graph recognition in linear time. I will conclude with the running times of our algorithm on classical benchmarks compared to those of other algorithms from the literature. Plus d'infos

 2010-03-05 Alon-Sack-Seymour Conjecture 14:00-15:00Salle 178 Finding a combinatorial proof for Graham-Pollak theorem have been a challenge for over 30 years. Though no such proof been found yet, such attempts have been fruitful in other ways. Some strengthening and extensions have been proved or conjectured. In this regard Alon Sack and Seymour conjectured that if the edge set of a graph G could be partitioned into n complete bipartite graphs then the chromatic number of G is at most n+1. In this talk we present a homomorphism approach to this conjecture. While we prove it for small values of n we expect the conjecture to fail for large values. We introduce some suspect toward this end. Plus d'infos

 2010-02-26 Introduction to eigenvalue methods in graph theory 14:00-15:00Salle 178 This will be an elementary introduction to application of eigenvalue methods in graph theory. Only basic knowledge of mathematics will be required. To make the talk more interesting for researcher we will do a proof of Graham-Pollak theorem. This theorem, which is introduce in relation with having a simple function to determine the distance of given pair of nodes in a large computer network, has only admitted proofs using linear algebra methods. All the attempt on finding a combinatorial proof, though fruitful in some other sense, been unsuccessful. Plus d'infos

 2010-02-19 Codes et graphes extenseurs 14:00-15:00Salle 178 Les graphes extenseurs (expander graphs) sont des familles de graphes pour lesquels tout sous-ensemble de sommets X suffisamment distinct de l'ensemble complet a un nombre de voisins au moins égal à cjXj pour une certaine constante c. Cette propriété se caractérise par un large écart entre les première et seconde valeurs propres du graphe. Les premières constructions de tels graphes remontent aux années 1980 et ont trouvé de nombreuses applications depuis, principalement dues à ce qu'ils ont des propriétés typiques de graphes aléatoires mais non triviales à obtenir constructivement. Or justement, les meilleurs codes correcteurs étant des codes aléatoires typiques, il est tentant d'essayer d'obtenir des bonnes constructions de codes par l'intermédiaire de graphes extenseurs. L'idée de construire des codes à l'aide d'un graphe et de petits codes linéaires constituants remonte à Tanner (1981) et pris son plein essor en 1996 grâce à un travail de Sipser et Spielman qui montrèrent, en s'appuyant sur la propriété d'expansion, que l'idée de Tanner permet à la fois la construction de codes binaires asymptotiquement bons et de garantir la correction d'un nombre d'erreurs proportionnel en la longueur du code n, le tout en temps quasi-linéaire en n. Nous présenterons cette construction ainsi qu'un certain nombre de variantes et de développements récents. Cette approche peut être vue comme intermédiaire entre le codage algébrique traditionnel et les méthodes plus modernes de décodage itératif impliquant les codes à matrice de parité creuse (LDPC). Plus d'infos

 2010-02-05 Domination de puissance 14:00-15:00Salle 178 La domination de puissance dans les graphes correspond à un problème de surveillance de l'état d'un réseau électrique à l'aide d'unités de mesure de phase. Contrairement aux autres paramètres de domination, ce paramètre introduit une possible propagation de l'ensemble des sommets dominés (lois de Kirchhoff), induisant des comportements similaires à celui des jeux dits "de la vie". Nous définirons précisément ce paramètre, et rappellerons les résultats existants ainsi que quelques preuves originales. Plus d'infos

 2010-01-29 6-star-coloring of subcubic graphs 14:00-15:00Salle 178 A star coloring of an undirected graph G is a proper vertex coloring of G (i.e., no two adjacent vertices are assigned the same color) such that no path on four vertices is 2-colored. The star chromatic number of G is the smallest integer k for which G admits a star coloring with k colors. In this paper, we prove that every subcubic graph is 6-star-colorable. Moreover, the upper bound 6 is best possible, based on the example constructed by Fertin, Raspaud, Reed in [G. Fertin, A. Raspaud, B. Reed, Star coloring of graphs. J. Graph Theory, 47(3): 140-153, 2004.] Plus d'infos

 2010-01-15 Bipartite subgraphs of triangle-free subcubic graphs. 14:00-15:00Salle 178 Plus d'infos

 2010-01-08 Coloration étoilée, partie 1 - 14:00-15:00salle 178 Premier exposé de 2 sur la coloration étoilée, le deuxième sera présenté le 29 janvier par Min Chen. Plus d'infos

Liste des événements répétitifs du groupe GT Graphes et Applications

Retour
Retour à l'index