2012-2013
2012 - 2013
Vendredi 14 septembre 2012 - Domination de puissance dans les graphes réguliers - Paul Dorbec.
Résumé :
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.
Vendredi 21 septembre 2012 - The Stretch Factor of $L_1$- and $L_\infty$-Delaunay Triangulations - Cyril Gavoille.
Résumé :
In this talk I will show that the stretch factor of $L_1$-Delaunay and $L_\infty$-Delaunay triangulations is equal to $\sqrt{4+2\sqrt{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+2\sqrt{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).
Vendredi 28 septembre 2012 - Complete oriented colourings and the oriented achromatic number - Eric Sopena.
Résumé :
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.
Vendredi 5 octobre 2012 - Algorithmes de graphes polynomiaux utilisant des automates (infinis) à compteurs. - Bruno Courcelle.
Résumé :
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.
Vendredi 12 octobre 2012 - La fonction theta de Lovasz est-elle unique? - Arnaud Pêcher
salle 76
Résumé :
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.
Vendredi 19 octobre 2012 - The game of Timber - Gabriel Renault.
Résumé :
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.
Vendredi 09 novembre 2012 - Computational complexity of partitioning a graph into a few connected subgraphs - Julien Bensmail.
Résumé : Let G be a graph. A sequence τ = (n1, ... , nk) of positive integers summing up to |V(G)| is realizable in G if there exists a partition (V1, ..., Vk) of V(G) such that each Vi induces a connected subgraph of G on ni 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.
Vendredi 30 novembre 2012 - Combinatorial properties of fullerene graphs - František Kardoš .
Résumé :
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.
Vendredi 7 décembre 2012 - Le nombre thêta de Lovász : applications, généralisations, et problèmes ouverts (1) - Christine Bachoc.
Exposé spécial WP6 Codes, Cryptologie, Algorithmique Arithmétique
Résumé :
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.
Vendredi 14 décembre 2012, 14h00- Comment avoir précisément 1/2 coup d'avance à un jeu - Paul Dorbec et Gabriel Renault.
Résumé :
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.
Vendredi 14 décembre 2012, 15h15 - Le nombre thêta de Lovász : applications, généralisations, et problèmes ouverts (2) - Christine Bachoc.
Exposé spécial WP6 Codes, Cryptologie, Algorithmique Arithmétique
Résumé :
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.
Vendredi 11 janvier 2013 - (Presque) tous les graphes fullerènes sont Hamiltoniens - František Kardoš .
Résumé :
Vendredi 18 janvier 2013 - Flots dans les graphes bidirigés - André Raspaud.
Résumé :
A signed graph (G, σ) is a graph G endowed with a signature σ, a mapping that assigns +1 or −1 to each edge. To obtain an orientation of a signed edge we divide it into two half-edges and we orient each half-edge independently fulfilling the following condition. If the edge is positive, one of its half-edges is oriented to and the other one from its end-vertex, if it is negative, then both half-edges are oriented either to or from their end-vertices. An oriented signed graph is also well
known as a bidirected graph. A nowhere-zero flow on a signed graph is, similarly as on a graph, an assignment of an orientation and a nonzero value from and abelian group A to each edge of a signed graph in such a way that the Kirchhoff’s law is fulfilled at each vertex: the sum of in-flowing values equals the sum of out-flowing values. In this talk we
will give a short survey about the existence of a nowhere-zero flow in bidirected graphs and intoduce the notion of circular flow on bidirected graphs. The circular flow number Φc (G, σ) of the underlying signed graph (G, σ) of a bidirected graph is the minimum r for which an orientation of (G, σ) admits a circular r-flow. We will present our following results (joint work with Xuding Zhu):
- If G is 4-edge connected and (G, σ) has a nowhere zero flow, then Φc (G, σ) (as well as Φ(G, σ)) is at most 4.
- If G is 6-edge connected and (G, σ) has a nowhere zero flow, then Φc (G, σ) is strictly less than 4.
We also will present the new key notion of imbalance ratio of an orientation of (G, σ) used in the proofs of the previous results.
Vendredi 25 janvier 2013 - Realizations in Domination game - Gašper Košmrlj.
Résumé : 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.
Mentionnons aussi le séminaire du GT combinatoire énumérative :
Vendredi 25 janvier 2013 - Propriétés asymptotiques de quelques classes de graphes à mineurs exclus - Mireille Bousquet-Mélou.
10h45 en salle 76
Résumé : Soit A une classe de graphes étiquetés, fermée pour l'extraction de mineurs. Soit G_n un graphe aléatoire de taille n pris uniformément dans A. Quand n est grand, quelle est la probabilité que G_n soit connexe ? Plus généralement, combien de composantes connexes a-t-il ? Grâce aux travaux de McDiarmid et de ses collaborateurs, ces questions sont désormais résolues lorsque tous les mineurs interdits sont connexes. C'est par exemple le cas des graphes planaires. Nous étudions, via une énumération exacte, une collection de classes A définies par l'interdiction de mineurs dont certains ne sont pas 2-connexes, et montrons que leur propriétés asymptotiques peuvent être très différentes de celles obtenues dans le cas de mineurs 2-connexes. Ces propriétés dépendent de la nature des singularités dominantes de la série génératrice C(z) qui compte les graphes connexes de A. Nous classons nos exemples selon cette nature, ce qui constitue un premier pas (modeste) vers une classification complète des classes de graphes closes par extraction de mineurs. (travail en commun avec Kerstin Weller, Oxford)
Vendredi 1 février 2013 - Problèmes de linéarisation/circularisation de graphes et hypergraphes motivés par l'assemblage de génomes - Cédric Chauve.
Résumé :
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).
Vendredi 8 février 2013 - Méthode de compression d'entropie et applications aux problèmes de coloration de graphes - Mickael Montassier (LIRMM).
Résumé : 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.
Vendredi 15 février 2013 - 3-Colourable Circulant Graphs - Joseph Peters (Simon Fraser Univ, Canada).
Résumé :
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.
Vendredi 8 mars 2013 - Facility location - Laurent Beaudou .
Vendredi 22 mars 2013 - Coloration localement irrégulière des arêtes d’un graphe - Julien Bensmail.
Résumé :
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.
Vendredi 29 mars 2013 15h15 - The complexity of signed graph homomorphisms. - Florent Foucaud.
Dans le cadre du WP6 du LabEx CPU
Résumé :
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.
Mercredi 3 avril 2013 - Journée spéciale graphes et structures géométriques
10h-11h30 - Quelques algorithmes entre le monde des graphes et les nuages de points - Soutenance d'HDR de Nicolas Bonichon
14h-15h - Un algorithme FPT simple exponentiel pour le problème Planar-F deletion - Christophe Paul (LIRMM, Montpellier)
Résumé : Soit F une famille de graphes. Le problème F-deletion consiste à tester s'il est possible de supprimer un ensemble d'au plus k sommets dans un graphe G pour obtenir un graphe H ne contenant pas de mineurs issus de F. Le cas F={K_2} correspond au problème Vertex Cover et F=K3 à Feedback Vertex Set. Si la famille F contient au moins un graphe planaire le problème est nommé Planar-F-Deletion. Nous proposons un algorithme FPT en simple exponentiel (i.e. en c{O(k).nO(1) ) pour Planar-F-deletion. Notre algorithme utilise la compression itérative, des règles de branchement et de réductions de protrusions. Le coeur de notre méthode est le calcul efficace d'une décomposition en protrusions (une décomposition utilisée dans de nombreux résultats). Nous présenterons l'algorithme et parlerons de ces conséquences.
15h30-16h30 - L'analyse simplifiée de la complexité de structures géométriques aléatoires - Olivier Deviller (Inria, Sophia-Antipolis)
Résumé : L'analyse en moyenne de structure de données et d'algorithmes géométriques est fréquemment utilisée en géométrie algorithmique, un domaine où l'analyse dans le cas le pire est souvent très pessimiste. La difficulté de ce type d'analyse fait que les modèles probabilistes utilisés restent simples et relativement éloignées de "données réalistes". Nous présentons une nouvelle approche pour l'analyse des structures géométriques. Nos résultats sont seulement à des facteurs logarithmiques près, mais notre méthode est plus simple que les classiques du domaine et nous réussissons à analyser de nouveau type de distribution liée à la smooth analysis.
Nous illustrons notre méthode sur deux structures classiques : l'enveloppe convexe et la triangulation de Delaunay. Plus précisément, nous démontrons simplement le fait, classique, que n points uniformément distribués dans une boule de R^d ont une enveloppe convexe et une triangulation de Delaunay dont l'espérance de la taille est respectivement Θ~(n(d-1)/(d+1)) et Θ~(n). Nous démontrons ensuite que si on se donne un ensemble de n points bien distribués sur une sphère, par exemple un $(\epsilon, \kappa)-échantillon de la sphère, et qu'on le perturbe ensuite en déplaçant chaque point uniformément d'une distance δ à partir de sa position initiale, alors l'espérance de la taille de l'enveloppe convexe de ces points est Θ~((√n)(1-1/d) (1/(4√δ)d-1/d).
Vendredi 5 avril 2013 - From edge-colouring to strong edge-colouring - Petru Valicov.
Résumé :
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.
Mardi 16 avril 2013 - 10h-11h -Identifying coDes in Evolving grAphs - Ralf Klasing.
Dans le cadre du séminaire LFANT - IMB, salle 385
Résumé : In this talk, we will give an overview of the ANR project "Identifying coDes in Evolving grAphs (IDEA)". In particular, we will present some of the results obtained in the project, and we will outline some potential directions of future research.
Vendredi 19 avril 2013 - Applications d'une preuve algorithmique du Lemme Local de Lovasz - Aline Parreau.
Résumé: Le lemme local de Lovasz est un outil très utilisé permettant de montrer de manière simple l'existence d'objets combinatoires avec certaines propriétés. Il dit que si des événements ont lieu avec une petite probabilité et ne sont pas trop indépendants les uns des autres, la probabilité qu'aucun évènement n'arrive est non nulle. Moser a donné en 2009 une preuve algorithmique de ce lemme, basée sur la compression d'entropie. Cette méthode permet en outre, dans certains cas, d'obtenir de manière élégante des résultats plus fort que ceux obtenus en utilisant le lemme local. J'expliquerai ses idées principales à travers deux exemples : la construction de mots sans carrés et la coloration acyclique des arêtes d'un graphe.
Travaux réalisés avec Louis Esperet (G-SCOP, Grenoble).
Vendredi 26 avril 2013 - Bad words arising from generalized Fibonacci cubes - Sandi Klavzar.
Vendredi 31 mai 2013 - Dicots, and a taxonomic ranking for misère games - Gabriel Renault.
Résumé :
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.
Vendredi 7 juin 2013 - Connexion arc en ciel dans les graphes orientés - Paul Dorbec.
Résumé : 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.
Vendredi 14 juin 2013 - Orientations "k-faibles" : un résultat de complexité - Julien Bensmail.
Résumé : 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.
Lundi 17 au Vendredi 21 juin 2013 - Ecole de théorie des graphes- .
voir http://oc.inpg.fr/conf/sgt2013/.
Vendredi 28 juin 2013 - Clique-Width, Tree-Width and Split Graphs - Tom Bouvier.
Résumé :
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.
Lundi 1 juillet 2013 - Graphs, games and propagation - Paul Dorbec.
Soutenance d'HDR, 10h45 en amphi du LaBRI
