Liste des événements uniques du groupe GT Graphes et Applications


2013-04-19Applications of an algorithmic proof of Lovasz Local Lemma
14:00-15:00
Salle 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-05From edge-colouring to strong edge-colouring
14:00-15:00
Salle 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-05une version dimensionnelle du théorème de Vosper
15:15-16:15
Salle 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-29The complexity of signed graph homomorphisms.
15:15-16:15
Salle 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-22Coloration localement irrégulière des arêtes d’un graphe
14:00-15:00
Salle 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-153-Colourable Circulant Graphs
14:00-15:00
Salle 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-08Méthode de compression d'entropie et applications aux problèmes de coloration de graphes
14:00-15:00
Salle 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-01Problèmes de linéarisation/circularisation de graphes et hypergraphes motivés par l'assemblage de génomes
14:00-15:00
Salle 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-25Realizations in Domination game
14:00-15:00
Salle 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-14Comment avoir précisément 1/2 coup d'avance à un jeu
14:00-15:00
Salle 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-14Le nombre thêta de Lovász : applications, généralisations, et problèmes ouverts (2)
15:15-16:15
Salle 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-30Combinatorial properties of fullerene graphs
14:00-15:00
Salle 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:00
Salle 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-19Le jeu de Timber
14:00-15:00
Amphi 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-12La fonction theta de Lovasz est-elle unique?
14:00-15:00
Salle 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-05Algorithmes de graphes polynomiaux utilisant des automates (infinis) à compteurs
14:00-15:00
Salle 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-28omplete oriented colourings and the oriented achromatic number
14:00-15:00
Salle 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-21The Stretch Factor of $L_1$- and $L_infty$-Delaunay Triangulations
14:00-15:00
Salle 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-14Domination de puissance dans les graphes réguliers
14:00-15:00
Salle 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-22Partitioning Harary graphs into connected subgraphs containing prescribed vertices
14:00-15:00
Salle 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-15Application de la théorie spectrale des graphes à des objets musicaux. Modélisation et visualisation en Hyperespace
14:00-15:00
Amphi 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-15Chemins disjoints avec congestion dans les graphes à mineur exclu
11:00-12:00
Amphi 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-11Complexity and algorithms for max-coloring problems
14:00-15:00
Salle 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-04Perfect matchings in cubic graphs
14:00-15:00
Salle 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-27Méthode d'accélération en optimisation global
14:00-15:00
Salle 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-13Arbitrarily Partionable Graphs
14:00-15:00
Salle 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-06Une (nouvelle?) décomposition canonique des graphes fortement connexes. Applications aux mots de Gauss
14:00-15:00
Salle 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-23Des codes (correcteurs) systématiques représentés sur une grille
14:00-15:00
Amphi 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-24Des limites de la coloration quasi propre
14:00-15:00
Salle 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-17Induced decomposition of graphs
14:00-15:00
Salle 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-10Petite histoire d'une petite preuve.
14:00-15:00
Salle 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:00
Salle 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-20Paired versus double domination in graphs
14:00-15:00
Salle 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-13Strong chromatic index of planar graphs with large girth
14:00-15:00
Salle 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-09Le théorème du sommet redondant pour les graphes sur les surfaces
14:00-15:00
Salle 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-02Bounded-Distance Network Creation Games
14:00-15:00
Salle 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-04On acyclic vertex colourings of graphs
15:15-16:15
Salle 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-04Rainbow numbers and rainbow connection
14:00-15:00
Salle 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-28Degré Minmax et Cycles Interdits
14:00-14:30
Salle 178
 Plus d'infos  


2011-10-28Énumération et élection dans les environnements de diffusion multisauts anonymes
14:30-15:00
Salle 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-21Partition arbitraire et préaffectation de sommets
14:00-14:30
Salle 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-21Vertex Nim : une variante de Nim dans les graphes
14:30-15:00
Salle 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-16Vizing conjecture or Krop's Theorem
14:00-15:00
Amphithé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-09Adjacent vertex-distinguishing edge-coloring of graphs
14:00-15:00
Salle 178
 Plus d'infos  


2011-07-01The 2-distance coloring of the Cartesian product of cycles using optimal Lee codes.
14:00-15:00
Salle 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-24Minmax Degree of Graphs
14:00-15:00
salle 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-10Computational Social Choice: Kemeny Scores and Parameterized Complexity
14:00-15:00
Amphi 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-09Discussion sur les principaux thèmes de recherche dans le domaine des graphes, de leur structuration, de l'algorithmique correspondante
11:00-12:00
Salle 178
 Plus d'infos  


2011-05-272-dipath and oriented L(2,1)-labelings of some families of oriented planar graphs
14:00-15:00
Salle 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-20Nowhere-zero flows in Cartesian bundles of graphs
14:00-15:00
Salle 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-13Rappels sur la méthode probabiliste en théorie des graphes
14:00-15:00
Salle 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-29Bounding the identifying code number of a graph using its degree parameters, a probabilistic approach
14:00-15:00
Salle 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-15Sur la difficulté de séparer un graphe par des plus courts chemins
14:00-15:00
Salle 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-08Nowhere-zero flows on signed eulerian graphs
14:00-15:00
Salle 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-01Décomposition de graphes
14:00-15:00
Salle 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-18Coloration d'arêtes à distance 2
14:00-15:00
Salle 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-11Le "disjoint path problem" et le "minor containement problem".
14:00-15:00
Salle 178
Je présenterai un algorithme polynomial pour résoudre ces deux problèmes.
 Plus d'infos  


2011-03-04An algorithmic decomposition of claw-free graphs leading to an O (n^3)-algorithm for the weighted stable set problem
14:00-15:00
Salle 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-18Testing Planarity of Partially Embedded Graphs
14:00-15:00
Salle 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-11Vertex partitions of graphs
14:00-15:00
Salle 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-04Graphes de très grande maille fondés sur les octonions
14:00-15:00
Grand 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-21Rainbow matchings: existence and counting
14:00-15:00
Salle 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-10Codes identifants, systèmes de contrôle et graphes sans-jumeaux.
14:00-15:00
Salle 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-03Largeur arborescente et dualité sur les surfaces
14:00-15:00
Salle 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-26Sur la dimension cubique de quelques classes d'arbres
14:00-15:00
Salle 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-22Une étude du jeu de Col
14:00-15:00
Salle 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-15Vertex distinguishing labelings of graphs
14:00-15:00
Salle 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-01Surveillance de réseaux éléctriques, Power Domination
14:00-15:00
Salle 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-17Problèmes ouverts de coloration et NP-completude
14:00-15:00
Salle 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-10Improved approximability and non-approximability results for graph diameter decreasing problems
14:00-15:00
Salle 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-25Autour du théorème de caractérisation des graphes sans mineur H
14:00-15:00
Salle 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-18Posets, dependent arcs, and colorings
14:00-15:00
Salle 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-08A linear time algorithm for L(2,1)-labeling of trees
10:00-11:00
Salle 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-04On packing of graphs, digraphs and hypergraphs
15:00-16:00
salle 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-28The doubly-critical graph conjecture
14:00-15:00
Salle 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-07Bin Packing avec Contrainte de Distance
14:00-15:00
salle 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-23Chemin séparabilité
14:00-15:00
salle 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-16Extremal cardinalities of identifying codes
14:00-15:00
Salle 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-09NP-complétude pour les colorations impropre, orientée et acyclique
14:00-15:00
Salle 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-02Problems from the cold
14:00-15:00
Salle 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-26The hidden matching-structure of the composition of strips
14:00-15:00
Salle 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-12Interval graphs and packing problem
14:00-15:00
Salle 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:00
Salle 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:00
Salle 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:00
Salle 178
Les graphes extenseurs (expander graphs) sont des familles de graphes pour lesquels tout sous-ensemble de sommets X suffisamment 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-05Domination de puissance
14:00-15:00
Salle 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-296-star-coloring of subcubic graphs
14:00-15:00
Salle 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-15Bipartite subgraphs of triangle-free subcubic graphs.
14:00-15:00
Salle 178
 Plus d'infos  


2010-01-08Coloration étoilée, partie 1 -
14:00-15:00
salle 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  


2009-12-11Sur le nombre chromatique ludique des chenilles
14:00-15:00
Salle 178
Nous nous intéresserons au problème de caractérisation des arbres de nombre chromatique ludique 3. Ce paramètre est défini à partir d'un jeu à deux joueurs ou chaque coup consiste à colorier un sommet, et dans lequel Alice essaye de colorier un graphe avec k couleurs et Bob tente de l'en empêcher. Une stratégie pour Alice assure une 4-coloration d'un arbre, donc d'une chenille. Mais dans quels cas Alice peut-elle gagner avec 3 couleurs? Dans cet exposé, nous montrerons quelles sont les chenilles sans sommets de degré 2 qui ont pour nombre chromatique ludique 3.
 Plus d'infos  


2009-12-04Spanner géométrique planaire de degré au plus 6
14:00-15:00
Salle 178
We consider the problem of constructing planar spanners of Euclidean graphs with the smallest maximum degree. We present a 6-spanner of degree bound by 6. The best previous bound on the degree of planar spanner was 14 with a stretch of $approx 3.53$. The spanner we proposed can be easily computed the Triangular Distance Delaunay triangulation introduced by Chew in 1989, that is known to have a stretch factor of 2 but its degree may not be bounded. (Travail réalisé en collaboration avec Cyril Gavoille, Nicolas Hanusse et Ljubomir Perković.)
 Plus d'infos  


2009-11-20Topological representations of planar partial cubes.
14:00-15:00
Salle 178
Partial cubes (distance preserving subgraphs of hypercubes) form a well studied class of graphs with nice metric properties.They appear in diverse areas, like: computer science, mathematical chemistry, mathematical biology, social sciences, psychology. In mathematics they have appeared, besides in graph theory and combinatorics, also in topology, algebra and computational geometry.

Tope graphs of oriented matroids are examples of partial cubes. One of the fundamental results about oriented matroids is the topological representation theorem. Topological representation theorem for planar partial cubes will be presented. Different realizations of a given partial cube and their connection to the face lattice of a partial cube will be also discussed.
 Plus d'infos  


2009-11-13Distance-two and incidence colorings of toroidal grids
14:00-15:00
Salle 178
The toroidal grid T(m,n) is the Cartesian product of two cycles of length m and n, respectively. In this talk, we shall present recent results and open questions related to distance-two and incidence colorings of toroidal grids. (joint work with Jiaojiao Wu)
 Plus d'infos  


2009-10-16Euler tour lock-in problem in the rotor-router model
14:00-15:00
salle 178
(joint work with E. Bampas, L. Gasieniec, N. Hanusse, R. Klasing, and A. Kosowski) The rotor-router model, also called the Propp machine, was first considered as a deterministic alternative to the random walk. It is known that the route in an undirected graph G=(V,E), where |V|=n and |E|=m, adopted by an agent controlled by the rotor-router mechanism forms eventually an Euler tour based on arcs obtained via replacing each edge in G by two arcs with opposite direction. The process of ushering the agent to an Euler tour is referred to as the lock-in problem. In a recent work, Yanovski et al. proved that independently of the initial configuration of the rotor-router mechanism in G the agent locks-in in time bounded by 2m diam, where diam is the diameter of G.

In this paper we examine the dependence of the lock-in time on the initial configuration of the rotor-router mechanism. The case study is performed in the form of a game between a player intending to lock-in the agent in an Euler tour as quickly as possible and its adversary with the counter objective.
 Plus d'infos  


2009-10-09Homomorphismes dans les graphes planaires
14:00-15:00
salle 178
The aim of this talk will be to introduce my main research project to the group. I will introduce some homomorphism problems on planar graphs, I will talk about their importance, will prove some results and will introduce some open problems, hopping for collaboration.
 Plus d'infos  


2009-10-02Coloration acyclique
14:00-15:00
Salle 178
Après avoir fait un bref rappel des notions de coloration acyclique et coloration acyclique par listes, j’en présenterai quelques résultats récents. Je m’attarderai tout particulièrement sur la coloration acyclique de graphes de degré maximum borné, mais aussi sur la coloration acyclique par listes de graphes planaires sans cycle de longueurs 4 à 12, pour laquelle nous utiliserons une procédure de déchargement…
 Plus d'infos  


2009-09-18Coloration quasi-propre
14:00-15:00
Salle 178
Je vous présenterai quelques résultats récents sur la coloration quasi-propre, notion qui généralise les notions de coloration propre et de coloration impropre.
 Plus d'infos  


2009-06-19Forme des arbres décomposables
14:00-15:00
Salle 076
Nous présenterons un résultat obtenu par Barth, Fournier et Ravaux concernant la forme des arbres décomposables.
 Plus d'infos  


2009-05-29Spanners Géométriques : liens étroits entre triangulations de TD-Delaunay et demi-Thêta-graphes
14:00-15:00
Salle 075
Un s-spanner est un sous-graphe H d’un graphe G, tel que pour tout couple de sommets, la distance dans H soit au plus s fois la distance dans G. Les Thêta-graphes sont une famille classique de spanner du graphe Euclidien (graphe complet sur n sommets du plan dont la longueur d'une arête est égale à la distance Euclidienne entre ses extrémités). Nous montrons qu’un demi-Thêta-graphe avec thêta = pi/3 est un 2-spanner du graphe Euclidien.

Pour obtenir ce résultat nous étudions les liens étroits qu’il y a entre les 1/2-théta-graphes, les surfaces orthogonales coplanaires et les triangulations de TD-Delaunay.

Nous présenterons également plusieurs résultats secondaires et généralisations possibles liés à ces correspondances.

(Travail réalisé en collaboration avec Cyril Gavoille, Nicolas Hanusse et David Ilcinkas).
 Plus d'infos  


2009-05-15On the Path Separability of Planar Graphs
14:00-15:00
Salle 075
It is known that every weighted planar graph with $n$ vertices contains three shortest paths whose removal halves the graph into connected components of at most $n/2$ vertices. Whether this property remains true with the use of two shortest paths only is an open problem.

We show that two shortest paths are enough for a large family of planar graphs, called face-separable, composed of graphs for which every induced subgraph can be halved by removing the border of a face in some suitable embedding of the subgraph. We also show that this non-trivial family of graphs includes unbounded treewidth graphs.
 Plus d'infos  


2009-04-24De l'incidence des matroides sur les arrangements, polytopes et noeuds, et pavages avec Frobenius
14:00-15:00
Salle 075
Dans cet exposé, je présenterai plusieurs résultats obtenus en utilisant la théorie des matroïdes orientés, liés aux problèmes géométriques (concernant les polytopes et les arrangements d'hyperplans) et topologiques (relatifs aux noeuds). J'aborderai également le problème diophantien de Frobenius, notamment dans le cadre d'une application récente à un problème de pavage.
 Plus d'infos  


2009-04-10Game coloring on the toroidal grid
14:00-15:00
Salle 075
A toroidal grid graph is the Cartesian product of two cycles. We prove that the maximum game chromatic number and maximum game coloring number of toroidal grids are equal to five.
 Plus d'infos  


2009-04-03Star coloring
14:00-15:00
Salle 075
A proper coloring of the vertices of a graph G is called a star-coloring if the union of every two color classes induces a star forest. The graph G is L-star-colorable if for a given list assignment L there is a star-coloring phi such that phi(v) is in L(v). If G is L-star-colorable for any list assignment L with |L(v)| at leat k for any vertex v, then G is called k-star-choosable. The star list chromatic number of a graph G is the smallest integer k such that G is k-star-choosable. In this talk we present new bounds for the star list chromatic number of subcubic planar graphs.
 Plus d'infos  


2009-03-20Graphes récursivement arbitrairement décomposables
14:00-15:00
Salle 075
Après un rappel des définitions et résultats sur les graphes arbitrairement sommet-décomposables, on présentera trois sous-classes de ces graphes : la version on-line, et les versions récursives et fortement récursives. On montrera que les graphes "fortement récursivement arbitrairement sommet-décomposables" (SR-AVD) sont exactement la classe des graphes claw-and-net free. Pour les "récursivement arbitrairement sommet-décomposables" (R-AVD), en s'appuyant sur des résultats précédents sur la version on-line, on donnera la liste exhaustive des arbres et soleils R-AVD, ainsi que quelques résultats sur un classe de graphes 2-connexes : les ballons.
 Plus d'infos  


2009-03-13Graph Searching Games and Routing Reconfiguration in WDM Networks
14:00-15:00
Salle 075
In graph searching games, a team of searchers is aiming at capturing an invisible fugitive running in a graph, or, equivalently, at clearing a contaminated network. These problems are motivated by several aspects of theoretical computer science, including computational complexity, minor graph theory and distributed algorithms. In this talk, we present a short literature survey and then, we focus on a more practical application, the routing reconfiguration problem in WDM networks. In this context, the goal consists in switching a set of connection requests from current routing to another pre-determined routing in order to optimize the resources of the network. We show how the problem can be modelled in terms of graph searching and present some results we obtained using this framework.
 Plus d'infos  


2009-03-06Le nombre d'arbres recouvrants de graphes de degré borné (suite)
14:00-15:00
Salle 075
Nous cherchons des bornes inférieures sur le nombre SP(G) d'arbres recouvrants d'un graphe connexe G de degré borné par d en termes de son nombre cyclomatique mu (nombre d'arêtes - nombre de sommets + 1). Nous définissons eta_d, inf{x|SP(G) ge x^mu(G) pour tout G connexe de degré borné par d} et nous conjecturons que eta_d est toujours donné par G=K_{d+1}. Cette conjecture est prouvée pour d=2, 3, 4 et 5 ; nous donnons des bornes inf sur eta_d pour d de 6 à 11.
 Plus d'infos  


2009-02-20Le nombre d'arbres recouvrants de graphes de degré borné
14:00-15:00
Salle 075
Nous cherchons des bornes inférieures sur le nombre SP(G) d'arbres recouvrants d'un graphe connexe G de degré borné par d en termes de son nombre cyclomatique mu (nombre d'arêtes - nombre de sommets + 1). Nous définissons eta_d, inf{x|SP(G) ge x^mu(G) pour tout G connexe de degré borné par d} et nous conjecturons que eta_d est toujours donné par G=K_{d+1}. Cette conjecture est prouvée pour d=2, 3, 4 et 5 ; nous donnons des bornes inf sur eta_d pour d de 6 à 11.
 Plus d'infos  


2009-02-13Nombre chromatique ludique des arbres et des chenilles
14:00-15:00
Salle 075
Le nombre chromatique ludique est issu d'un jeu de coloration [G,k] à deux joueurs où Alice tente de colorier tout graphe G avec k couleurs et Bob essaye de l'en empêcher. Ce nombre est le plus petit k pour lequel Alice a une stratégie gagnante, en jouant la première. Si Bob joue le premier coup, on parlera de nombre chromatique ludique misère. Comme tout arbre a un nombre chromatique ludique d'au plus 4 (et d'au moins 3 s'il est de diamètre supérieur à 4), il est intéressant de caractériser les arbres de nombre chromatique ludique 3. Nous montrerons comment caractériser les 1-chenilles de nombre chromatique ludique 3. Dans le cas des arbres généraux, nous présenterons quelques réductions qui permettent de limiter l'étude du problème à une famille plus restreinte d'arbres.
 Plus d'infos  


2009-01-30Consecutive ones matrices for orthogonal packing problems
14:00-15:00
Salle 075
La modélisation par des graphes par Feketete et Shepers (1997) du problème du placement de formes orthogonales dans un conteneur a permis de faire un saut quantitatif quant à la taille des problèmes traités. En effet, en représentant les solutions par des graphes d'intervalles, de nombreuses symmétries (i.e. des solutions identiques) sont éliminées.
Fulkerson et Gross ont démontré qu'un graphe est un graphe d'intervalle si et seulement s'il a au plus n cliques maximales (n étant son nombre de sommets), et celles-ci peuvent être ordonnées, de telle sorte que pour tout sommet, les cliques le contenant soient consécutives. Avec Cédric Joncour, nous* avons mis au point un nouvel algorithme basé sur cette caractérisation des graphes d'intervalles. Mon exposé présentera les grandes lignes de cet algorithme et les résultats obtenus sur les jeux de tests classiques. Il n'y aura donc pas de polytopes (sic) et pas beaucoup de maths non-plus (re-sic).

nous* = surtout Cédric"
 Plus d'infos  


2009-01-23Adding a distance constraint to Bin Packing and Bin Covering Problems
14:00-15:00
Salle 075
Nous nous intéressons à deux problèmes NP-Complet classiques, le Bin
Covering et le Bin Packing, admettant respectivement un PTAAS et un
PTAS. Nous étudions une version contrainte de ces problèmes, lorsque les
éléments à grouper se trouvent à une certaine
distance les uns des autres. Le but est d'alors de former des groupes
d'éléments ayant au moins un certain poids (resp. au plus un certain
poids) de façon à ce que deux éléments présents dans le même groupe ne
soient pas à une distance supérieure à une certaine borne fixée dans
l'instance du problème.
Pour ces deux problèmes de Bin Covering et de Bin Packing avec Distance
Contrainte, nous démontrons l'impossibilité d'approximer à n'importe
quelle constante chacun des deux problèmes en les réduisant pour l'un au
problème du Maximum k-Dimensional Matching, et, pour l'autre, au
problème de Minimum Clique Partition. Ces résultats d'inapproximabilité
sont étendus au cas où la contrainte de distance est relâchée en
utilisant une augmentation de ressource: une solution est autorisée à
construire des groupes de diamètre (2-e).dmax, e>0, tandis qu'elle sera
toujours comparé à l'optimal contraint à dmax.

Nous présentons ensuite pour chacun de ces deux problèmes un algorithme
d'approximation utilisant respectivement une augmentation de ressource
sur le diamètre de 3 et de 2, permettant une approximation de la
solution optimale à respectivement un facteur 1/3 et 3.
 Plus d'infos  


2008-12-19Compter les couplages parfaits dans les graphes cubiques
14:00-15:00
salle 075
Lovasz et Plummer ont conjecturé dans les années 70 que les graphes cubiques 2-arête-connexes ont un nombre exponentiel de couplages parfaits. Cela a été montré pour les graphes bipartis en 1979 par Voorhoeve, et très récemment pour les graphes planaires par Chudnovsky et Seymour. Dans le cas général les meilleures bornes connues sont linéaires : Edmonds, Lovász, et Pulleyblank, et indépendamment Naddef, ont prouvé en 1982 que la dimension du polytope des couplages parfaits d'un graphe cubique 2-arête-connexe a n sommets est au moins n/4+1 (ce qui implique directement qu'ils ont au moins n/4+2 couplages parfaits). En utilisant un résultat récent de Král', Sereni, et Stiebitz, nous montrons que tout graphe cubique 2-arête-connexe a n sommets a au moins 3n/4-10 couplages parfaits. Notre preuve est inductive et repose largement sur la "brick and brace decomposition" introduite par Edmonds, Lovász, et Pulleyblank en 1982.

(travail en commun avec Daniel Král, Petr ¦koda, et Riste ¦krekovski)
 Plus d'infos  


2008-12-12Structure des graphes sans mineur K_2,4
14:00-15:00
salle 075
Nous nous intéressons à la structure des graphes ne contenant
pas comme mineur un graphe H. De nombreuses caractérisations sont
connues lorsque H contient au plus 5 sommets, en particulier pour
H=K_5 [Wagner - 1937]. Le problème est beaucoup plus difficile lorsque
H contient 6 sommets, voir plus. Par exemple, la caractérisation des
graphes sans mineur K_6 est toujours non résolue, et est en relation
avec la conjecture d'Hadwiger concernant le nombre chromatique des
graphes sans K_r (voir [K. Kawarabayashi - SODA'07] pour une plus
ample discussion sur l'importance des graphes sans mineur K_6). Citons
également la conjecture de Jörgensen - 1994:

Conjecture: Tout graphe 6-connexe G sans mineur K_6 possède un sommet
u tel que G{u} est planaire.

Nous prouvons le résultat suivant:

Théorème: Tout graphe 2-connexe G sans mineur K_{2,4} possède deux
sommets u,v tels que G{u,v} est planaire-extérieur.

En particulier, les graphes sans mineur K_{2,4} sont de largeur
arborescente au plus 4, améliorant un résultat de [Bodlaender et al. -
1997]. Cette borne est optimale à cause de K_5. En fait, nous
construisons un algorithme de complexité linéaire qui pour tout graphe
2-connexe soit exhibe un mineur K_{2,4} ou bien détermine deux sommets
dont la suppression rend le graphe planaire-extérieur.

Le théorème précédent ne peut pas être étendu trivialement pour les
graphes sans mineurs K_{2,r} avec r > 4. En effet, nous montrons que
pour tout entier k, il existe un graphe 2-connexe sans mineur K_{2,5}
pour lequel il est nécessaire d'enlever k sommets pour le rendre
planaire-extérieur.
 Plus d'infos  


2008-12-05Mots, graphes et morphismes sans répétition : quelques résultats et questions
13:00-14:00
salle 075
La résolution de nombreux problèmes nécessite une bonne compréhension de phénomènes de répétitions dans les mots. Une première partie de l'exposé présentera quelques résultats récents sur un problème ouvert dans les années 1980 : est-il possible de décider si un morphisme préserve les mots sans puissance k ? Une deuxième partie de l'exposé s'interrogera sur la généralisabilité d'une telle approche aux graphes sans répétition introduits récemment par Alon, Grytczuk et al.
 Plus d'infos  


2008-11-14Résumé de cubes de données
14:00-15:00
salle 075
Un cube de donnée est une structure de donnée utilisée en fouille de données. Elle peut être modélisée par un hypercube orienté, étiqueté et pondéré. L'objectif de ce travail est de construire un ensemble de sommets S de petite taille tel que tout sommet possède un ancêtre dans S de poids comparable.

 Plus d'infos  


2008-10-10Periodic exploration using an agent with small memory
14:00-15:00
075
We consider the problem of periodic graph exploration in which a mobile entity with constant memory, an agent, has to visit all n nodes of an arbitrary undirected graph G in a periodic manner. Graphs are supposed to be anonymous, that is, nodes are unlabeled. However, while visiting a node, the robot has to distinguish between edges incident to it. For each node v the endpoints of the edges incident to v are uniquely identified by different integer labels called port numbers. We are interested in minimisation of the length of the exploration period.

This problem is unsolvable if the local port numbers are set arbitrarily, see [Budach 1978]. However, surprisingly small periods can be achieved when assigning carefully the local port numbers. Dobrev et al. [SIROCCO 2005] described an algorithm for assigning port numbers, and an oblivious agent (i.e. agent with no memory) using it, such that the agent explores all graphs of size n within period 10n. Providing the agent with a constant number of memory bits, the optimal length of the period was proved in [Gasieniec et al. JCSS 2008] to be no more than $3.75n$ (using a different assignment of the port numbers). In this paper, we improve both these bounds. More precisely, we show a period of length at most (4+1/3)n for oblivious agents, and a period of length at most 3.5n for agents with constant memory. Moreover, we give the first non-trivial lower bound, 2.8n, on the period length for the oblivious case.
 Plus d'infos  


2008-09-05Jeux de colorations dans les graphes
14:00-15:00
salle 076
On considère un jeu dans lequel deux joueurs (Alice et Bob) colorient tour à tour les sommets d'un graphe avec un nombre donné de couleurs (de manière à ce que deux sommets adjacents aient des couleurs distinctes). Si à la fin le graphe est entièrement colorié, Alice gagne. Sinon Bob gagne (cela signifie qu'à un moment, un sommet non colorié a toutes les couleurs disponibles dans son voisinage... aucun des deux joueurs ne peut donc le colorier).

Je dirai quelques généralités sur ce jeu introduit par Boadlander en 1991, et on essaiera de voir quelles techniques peuvent être utilisées pour trouver des stratégies gagnantes pour Alice ou pour Bob.
 Plus d'infos  


2008-06-20Compositions de jeux combinatoires : le jeu de domination sur les chemins
14:00-15:00
Salle 75
Le jeu de domination est un jeu à deux joueurs qui jouent alternativement sur un graphe non orienté G. À chaque tour, un joueur supprime un sommet ainsi que l'ensemble de ses voisins. En version 'normale', le joueur qui supprime le dernier sommet gagne la partie. En version 'misère', le joueur qui supprime le dernier sommet perd la partie. L'étude d'un tel jeu consiste d'une part à déterminer si une position de jeu est gagnante ou perdante pour le joueur qui doit jouer, et d'autre part à définir la stratégie gagnante (lorsque la position est gagnante).

Lorsque le graphe G est non connexe, le jeu peut être vu comme une 'composition' des jeux sur chaque composante connexe. Le jeu de domination, tel que nous l'avons décrit, correspond à la 'somme disjonctive' des jeux sur les composantes connexes : un joueur choisit l'une des composantes, puis supprime un sommet et ses voisins dans cette composante.

Dans son livre "On Numbers and Games", H. J. Conway a proposé 12 façons de jouer sur des compositions de jeux combinatoires. Nous présenterons ces 12 versions et, dans le cas du jeu de domination sur des chemins, résoudrons 10 de ces 12 versions.
 Plus d'infos  


2008-06-13Dualité de certains paramètres de largeur de graphes (à la recherche de LA preuve...)
14:00-15:00
Salle 75
Certains paramètres de graphes admettent des caractérisations min/max. L'une de ces caractérisations les plus connue est le théorème de dualité tree-width/bramble number de Seymour et Thomas. Avec O. Amini, N. Nisse et S. Thomassé, nous avons développé un cadre général permettant de prouver un grand nombre de ces théorèmes. Plus récemment, avec L. Lyaudet et S. Thomassé, nous avons grandement simplifié ce cadre pour le généraliser encore un peu. Ce sont ces travaux que je compte vous présenter.
 Plus d'infos  


2008-06-06Nowhere-zero flows in Cayley graphs
14:00-15:00
Salle 75
The celebrated 5-Flow Conjecture of Tutte (1954) suggests that
every bridgeless graph admits a nowhere-zero 5-flow. As highly
symmetric graphs seem unlikely to require 5-flows, Alspach, Liu,
and Zhang (1996) proposed a conjecture that every Cayley graph of
valency at least 3 has a nowhere-zero 4-flow. Furthermore, if
Tutte's 3-Flow Conjecture is true, every Cayley graph of valency
at least 4 will have a nowhere-zero 3-flow.

In the talk we will report about the status of Tutte's flow
conjectures in this largely unexplored area, and will verify his
3-Flow Conjecture for Cayley graphs on a class of groups that
includes all nilpotent groups.
 Plus d'infos  


2008-05-23On (1,2) conjecture
14:00-15:00
Salle 178
Let us assign positive integers to the edges and vertices of a simple graph G. As a result we obtain a vertex-colouring of G by sums of weights assigned to the vertex and its adjacent edges. Can we obtain a proper coloring using only weights 1 and 2 for an arbitrary G?
 Plus d'infos  


2008-04-18Nouvelles perspectives sur le problème de 3-coloration
14:00-15:00
Salle 75
Je présenterai une nouvelle approche du problème de 3-coloration des graphes planaires basée sur l'adjacence des cycles, ainsi qu'un renforcement d'un théorème de Borodin et al [JCTB, 93:303-311, 2005].
 Plus d'infos  


2008-04-11Polytope des cliques circulaires et calcul du nombre d'indépendance
14:00-15:00
Salle 75
Un résultat majeur de la théorie des graphes est que le nombre
chromatique d'un graphe parfait est calculable en temps polynomial
(Grotschel, Lovasz et Schrijver). Le nombre circulaire chromatique est
un raffinement du nombre chromatique usuel d'un graphe. Xuding Zhu a
mis en évidence que les cliques circulaires sont le pendant naturel
des cliques pour les colorations circulaires. Ceci lui a permis de
définir élégamment les graphes circulaires-parfaits, une famille de
graphes contenant strictement les graphes parfaits. La complexité du
calcul du nombre circulaire chromatique d'un graphe circulaire parfait
est inconnue.

Nous introduisons le polytope des cliques circulaires, un polytope
dont les points extrémaux sont en correspondance avec les cliques
circulaires induites d'un graphe, et nous montrons à l'aide de
celui-ci et le résultat de Grotschel, Lovasz et Schrijver déjà
mentionné, que le nombre (circulaire) chromatique d'un graphe
fortement circulaire-parfait est calculable en temps polynomial (les
graphes fortement circulaire-parfaits étant une famille intermédiaire
entre les graphes parfaits et les graphes circulaire-parfaits).

Une autre application, plus inattendue, de ce polytope est qu'en le
combinant avec la caratérisation des facettes du polytope des stables
d'un graphe proche-biparti de Shepherd, nous avons pu établir que le
nombre d'indépendance d'un graphe circulaire d'intervalles flou (une
famille de graphes sans griffe essentielle selon Chudnovsky et
Seymour) est calculable en temps polynomial. Il s'agit de la première
preuve de ce résultat de nature polyédrale, mais elle est limitée au
cas non-pondéré. Pour la version pondérée, une compréhension plus fine
du polytope des stables reste nécessaire.
 Plus d'infos  


2008-04-04Routage dans les "arbres de graphes planaires-extérieurs de genre-r"
14:00-15:00
Salle 75
Dans cet exposé nous parlerons de schéma de routage de plus court chemin dans les graphes valués. Nous étudierons les "arbres de graphes planaires-extérieurs de genre-r" une sur-classe des graphes planaires-extérieurs. Ce résultat étend le schéma de routage avec des tables de O(log n) bits vérifié dans les arbres et les graphes planaires-extérieurs non valués à n sommets, vers une classe de graphes valués beaucoup plus grande, contenant par exemple des graphes de genre non borné.

Nous avons utilisé des propriétés du routage par intervalles. A cette occasion nous parlerons de cette méthode à travers laquelle une relation a été mise en évidence par Bodleander et al. en 1997, entre la théorie du routage compact, la largeur arborescente et la théorie des mineurs exclus.
 Plus d'infos  


2008-03-28Empilements et recouvrements dans les graphes
14:00-15:00
Salle 75
Les problèmes d'empilements et de recouvrements, certes moins populaires que les problèmes de coloration, sont néanmoins des problèmes fondamentaux de la théorie des graphes. En particulier, on peut relier les problèmes d'empilement à une bonne partie de la théorie des codes correcteurs. De plus, la domination est un problème de recouvrement qui attire largement l'attention, comme le prouve la vaste littérature sur le sujet.

Au cours de cet exposé, nous parlerons d'abord de paire-domination, une variante de la domination introduite par Haynes et Slater. Nous verrons quels sont les cas critiques pour ce paramètre, et quelles bornes l'exclusion de ces cas permet d'obtenir. Puis, nous continuerons l'étude des codes pondérés entamée par Cohen, Honkala, Lytsin et Mattson. Dans le cas parfait, un code pondéré de rayon 1 nécessite une certaine régularité qui nous permet de déterminer dans la plupart des cas l'existence ou l'inexistence de codes.
 Plus d'infos  


2008-03-21Permutations de Baxter et orientations bipolaires planes
14:00-15:00
Salle 75
Nous présenterons une bijection directe entre les permutations de Baxter de
taille n et les orientations bipolaires planes à n arêtes. Cette bijection transporte
plusieurs paramètres classiques des permutations de Baxter (nombre de montées, nombre de
descentes, nombre de saillants supérieurs gauches...) vers des paramètres tout aussi
classiques des orientations bipolaires planes (nombre de faces internes, nombre de
sommets, degré du puits...). De plus, cette bijection produit des dessins polylines
compacts pour les cartes considérées. Nous présenterons également 2 spécialisations de
cette bijection.
Travail réalisé en collaboration avec Mireille Bousquet-Mélou et Eric Fusy.
 Plus d'infos  


2008-03-14Représentation distribuée de distances dans les graphes
14:00-15:00
Salle 75
La représentation distribuée d'un graphe consiste à stocker sur chaque sommet du graphe une information utile permettant la résolution de requête de manière locale, c'est-à-dire en examinant seulement l'information stockée par les sommets concernés par la requête. On s'intéresse ici au cas de la requête de distance bornée, c'est-à-dire déterminer la distance entre deux sommets si celle-ci est inférieure à un paramètre k fixé. Notre principale contribution est une représentation de distance bornée pour les arbres de n sommets utilisant log n +O(k log(k log n)) bits par sommets. La représentation obtenue permet en fait des requêtes plus complexes que de simples tests de distance et a des applications pour les recherches dans les fichiers XML.
 Plus d'infos  


2008-03-07Etiquetage de propriétés du premier ordre dans des graphes de largeur de clique non bornée (suite)
14:00-15:00
Salle 75
Suite de l'exposé du 1er février

Un graphe est "locally cwd-decomposable" si quelque soit un entier r, on peut couvrir le graphe avec des boules tel que :
- pour tout sommet son voisinage de rayon r est inclus dans une boule
- le graphe d'intersection des boules est de degré au plus d
- chaque boule est de clique-width au plus w
- d et w dépendent de r
- cette couverture peut etre calculée en temps polynomial

Cette classe contient par exemple les planaires, les graphes de degré borné, les unit-interval graphes ou les classes de graphes clos par mineurs et qui ne contiennent pas tous les apex.

Nous allons montrer que pour toute formule du premier ordre, il existe un schéma d'etiquetage de taille O(log(n)) dans la classe de graphes "locally cwd-decomposable". Un résultat de ce type sera montré aussi pour les classes d'expansion bornée, mais avec une logique plus faible.

Si on a le temps, je montrerai comment étendre le premier résultat au comptage.

(travail en commun avec B. Courcelle et C. Gavoille).
 Plus d'infos  


2008-02-15Hypohamiltonian cubic graphs of girth 7
14:00-15:00
Salle 75
Deciding whether a given graph is hamiltonian is a well known NP-complete problem which remains NP-complete even within the family of cubic graphs. Hypohamiltonian graphs -- graphs for which the removal of an arbitrary vertex leaves a hamiltonian graph -- lie on the border between the class hamiltonian graphs and its complement. Better understanding of hypohamiltonian graphs can therefore lead to demarcation line for hamiltonian graphs.

Roughly speaking, the higher girth and cyclic connectivity, the harder is to find a hypohamiltonian graph with these parameters. Moreover, Thomassen conjectured, that there exists a constant $k$ (possibly $k=8$) such that every cyclically k-edge-connected cubic graph is hamiltonian. Interesting in this sense is the Coxeter graph, having both girth and cyclic connectivity 7, for it is the only highly connected graph of girth at least 7 that is known to be hypohamiltonian.

We provide a construction, which uses as building blocks a graph derived from the Coxeter graph, giving rise to an infinite family of cubic hypohamiltonian graphs of girth 7, with cyclic connectivity 4, 5, or 6.

This is a joint work with Martin ¦koviera.
 Plus d'infos  


2008-02-08Beau quasi-ordre de fonctions de re-étiquetage
14:00-15:00
Salle 75
Un pré-ordre (Q,<=) est bien-quasiment-ordonné, (ou "WQO" pour "Well-quasi-ordered") si pour toute séquence infinie (x_i) d'éléments dans Q, il existe i < j tels que x_i <= x_j.

Robertson et Seymour montrent (dans leur série d'articles sur les mineurs de graphes) la conjecture de Wagner, qui dit que la classe de tous les graphes est WQO par mineurs. Cela prouve par exemple que toutes les classes fermées par mineurs ont un nombre fini d'exclusions, généralisant ainsi le théorème de Kuratowski caractérisant les graphes planaires.

Il existe d'autres relation entre les graphes à explorer. On s'intéresse ici à la relation de sous graphe induit.

On définit une restriction de la grammaire de graphes NLC, que l'on note NLC^F, où les fonctions de re-étiquetage appartiennent à un ensemble fixé F. On donne une condition nécessaire et suffisante sur F pour que la classe NLC^F soit WQO.

(Travail en commun avec J. Daligault et S. Thomassé.)
 Plus d'infos  


2008-02-01Etiquetage de propriétés du premier ordre dans des graphes de largeur de clique non bornée
14:00-15:00
Salle 75
Un graphe est "locally cwd-decomposable" si quelque soit un entier r, on peut couvrir le graphe avec des boules tel que :
- pour tout sommet son voisinage de rayon r est inclus dans une boule
- le graphe d'intersection des boules est de degré au plus d
- chaque boule est de clique-width au plus w
- d et w dépendent de r
- cette couverture peut etre calculée en temps polynomial

Cette classe contient par exemple les planaires, les graphes de degré borné, les unit-interval graphes ou les classes de graphes clos par mineurs et qui ne contiennent pas tous les apex.

Nous allons montrer que pour toute formule du premier ordre, il existe un schéma d'etiquetage de taille O(log(n)) dans la classe de graphes "locally cwd-decomposable". Un résultat de ce type sera montré aussi pour les classes d'expansion bornée, mais avec une logique plus faible.

Si on a le temps, je montrerai comment étendre le premier résultat au comptage.

(travail en commun avec B. Courcelle et C. Gavoille).
 Plus d'infos  


2008-01-25Coloration adaptable des graphes planaires
14:00-15:00
Salle 75
Étant donnée une coloration F (potentiellement impropre) des arêtes d'un graphe G, une coloration des sommets de G est dite "adaptée" à F si aucune couleur n'apparaît à la fois sur une arête et sur ses deux extrémités. Le nombre chromatique adaptable de G est le plus petit entier k, tel pour toute arête-coloration F de G, G admet une k-coloration adaptée à F.

Je ferai un rapide survol des résultats connus sur cette coloration (introduite récemment par Pavol Hell et Xuding Zhu), et j'expliquerai ensuite des résultats que nous avons obtenus avec Mickaël Montassier et Xuding Zhu sur le nombre chromatique adaptable des graphes planaires.
 Plus d'infos  


2008-01-18Graphes de démonstration, cographes et couplages parfaits
14:00-15:00
Salle 75
Les preuves de la logique linéaire [1] peuvent se voir comme une classe inductive de graphes munis d'un couplage parfait (disons des arêtes bleues) dont les autres arêtes (disons rouges) forment un cographe et cette classe inductive de graphes est caractérisée par la présence, sur tout cycle élémentaire alternant d'une corde rouge [2]. Pour la logique linéaire non commutative dont les preuves correspondent à des dérivations dans des grammaires hors-contexte, ce résultat s'étend: les graphes doivent être orientés , une troisième couleur est nécessaire et la condition inclut une forme de bon parenthésage [3]. Pour une variante de la logique linéaire [4] qui ajoute aux connecteurs commutatif un connecteur non commutatif et autodual, qui correspondent à des cographes orientés, dont certains complets bipartis Kn,p sont orientés (de la partie "n" vers la partie "p"), nous n'avons pas de résultat, mais une conjecture sur laquelle je recherche de l'aide...

[1] Girard, J.-Y. : Linear Logic, Theoretical Computer Science, 50:1, pp. 1-102, 1987.

[2] Christian Retoré Handsome proof nets: perfect matchings and cographs. Theoretical Computer Science. 294(3), 2003, pages 473488 [Version complète: RR-3652.]

[3] Sylvain Pogodalla and Christian Retoré Handsome Non-Commutative Proof-Nets: perfect matchings, series-parallel orders and Hamiltonian circuits INRIA RR-5409 Work presented at Categorial grammars 2004, LIRMM, Montpellier, juin 2004. To appear in Journal of Applied Logic

[4] Christian Retoré Pomset logic: a non-commutative extension of classical linear logic In TLCA'97, LNCS vol. 1210, pp 300--318.
 Plus d'infos  


2008-01-11Colorations orientées des graphes planaires
14:00-15:00
Salle 75
Dans cet exposé, je vous présenterai de nouveaux résultats récemment obtenus pour la coloration orientée de certaines sous classes de graphes planaires. Rappelons qu'une sommet-coloration orientée d'un graphe orienté antisymétrique est une partition des sommets du graphe en stables de telle sorte que les arcs reliant toute paire de stables aient la même direction. Je vous montrerai alors que tout graphe planaire de maille au moins 5 possède une coloration orientée avec au plus 16 couleurs, ce qui améliore la précédent borne connue qui était de 19.

Dans un second temps, je parlerai d'arc-coloration orientée. Cette coloration se définit de manière naturelle à partir de la sommet-coloration orientée : une arc-coloration orientée d'un graphe orienté correspond une sommet-coloration orientée de son line-graph. Je vous montrerai les résultats que nous avons récemment obtenu pour l'indice chromatique orienté des 2-arbres partiels de maille donnée.
 Plus d'infos  


2007-12-14Une relaxation du problème de Havel
14:00-15:00
Salle 75
En 1976, Appel et Haken ont prouvé que tout graphe planaire est 4-coloriable. Grötzsch quant à lui a montré que tout graphe planaire sans triangle est 3-coloriable en 1963. En 1970, Havel s'interroge sur le problème suivant : si on prend un graphe planaire G contenant des triangles, mais ceux-ci étant suffisamment éloignés les uns des autres ; est-ce que G est 3-coloriable ? Existe t-il une constante d telle que tout graphe planaire ayant leurs triangles à distance au moins d est 3-coloriable ? À ce jour, personne n'a démontré l'existence de d, ni n'a proposé de contre-exemples pour d quelconque.

Dans cet exposé, nous proposerons une relaxation du problème de Havel et tenterons d'apporter quelques réponses à cette relaxation.
 Plus d'infos  


2007-12-07On the growth rate of minor-closed classes of graphs
14:00-15:00
Salle 75
We study the enumerative properties of minor-closed classes of
(labeled) graphs.

Recall that a graph H is a minor of a graph G if H can be obtained
from G by a sequence of edge-deletion and edge-contraction. Hence, a
class of graph is closed under minor if this class is closed by
edge-deletion and edge-contraction. For instance, the class of forest
and the class of planar graphs are closed under minor.

It was shown by Norine, Seymour, Thomas and Wollan that for any proper
minor-closed class of graphs G, the number g_n of graphs in G grows
slower than c^n*n! for some constant c=c(G) (to be compared with the
total number of graphs n^(n(n-1)/2)). In this talk, we will
investigate the possible asymptotic behavior for g_n. We will see, for
instance, that this behavior is either
- polynomial: n^a - exponential: a^n - or factorial: n^(n/2)
We then investigate the possible growth rate of the classes that have
a factorial behaviour.

This is a joint work with Marc Noy and Dominic Welsh.
 Plus d'infos  


2007-11-23Jeux combinatoires sur les graphes
14:00-15:00
Salle 75
La résolution des jeux combinatoires à deux joueurs, ou jeux sans hasard, consiste à rechercher un ensemble absorbant dans le "graphe d'états" du jeu qui, dans notre cas, est sans cycle (on ne peut revenir à une position antérieure).
Cet ensemble absorbant est l'ensemble des états (ou positions) perdants pour le joueur suivant.

Nous verrons plusieurs exemples de jeux de coloration de sommets, où la règle de base est:
- Partant d'un graphe G et d'un nombre k de couleurs, on colorie le graphe avec les k couleurs
- Le premier joueur ne pouvant plus colorier de sommet est déclaré perdant.

Si l'on se limite à deux joueurs, le problème est de classer les graphes en deux familles: ceux qui offrent au joueur A la possibilité de gagner, et les autres.
Nous utiliserons la fonction de Grundy, qui permet de savoir si A peut gagner, qui permet de déterminer les stratégies de jeu, et qui s'exprime en fonction des valeurs de Grundy des composantes connexes du graphe.
Comme la résolution de ce problème est exponentiel en fonction de la taille du graphe, et comme aucune heuristique n'est satisfaisante, on se limitera à rechercher des familles dont la fonction de Grundy est soit connue (périodique) , soit calculable en temps polynômial.

Enfin, nous verrons que, dans d'autres jeux de coloration, la fonction de Grundy n'est pas utilisable, et donc la résolution de ceux-ci est encore plus difficile.
 Plus d'infos  


2007-11-16On the hardness of constructing minimal 2-connected spanning subgraphs in complete graphs with sharpened triangle inequality
14:00-15:00
Salle 75
In this talk we investigate the problem of finding a 2-connected spanning subgraph of minimal cost in a complete and weighted graph G. This problem is known to be APX-hard, both for the edge- and for the vertex-connectivity case. Here we prove that the APX-hardness still holds even if one restricts the edge costs to an interval [1, 1+epsilon], for an arbitrary small epsilon. This result implies the first explicit lower bound on the approximability of the general problems.

On the other hand, if the input graph satisfies the sharpened beta- triangle inequality, then a (2/3+1/3*beta/(1-beta))-approximation algorithm is designed. This ratio tends to 1 with beta tending to 1/2, and it improves the previous known bound of 3/2, holding for graphs satis- fying the triangle inequality, as soon as beta < 5/7.

Furthermore, a generalized problem of increasing to 2 the edge-connectivity of any spanning subgraph of G by means of a set of edges of minimum cost is considered. This problem is known to admit a 2-approximation algorithm. Here we show that whenever the input graph satisfies the sharpened beta- triangle inequality with beta < 2/3, then this ratio can be improved to beta/(1-beta).
 Plus d'infos  


2007-10-23Counting planar graphs and directed cycle double covers by matrix integrals
14:00-15:00
Salle 75
This is a joint work with Mihyun Kang. First I briefly introduce matrix integrals as a useful technics in combinatorics.

I will show how matrix integrals of combinatorially defined functions count object of interest in graph theory: graphs embeddable on surfaces (e.g. planar graphs), and graphs with a specified directed cycle double cover. So far, to my knowledge, only matrix integrals of functions of traces were considered in combinatorics. These count maps, not embeddable graphs. It turns out that the combinatorially defined function we integrate may have interpretation as determinants or permanents.
 Plus d'infos  


2007-10-12Coloration frugale des graphes
14:00-15:00
Salle 75
Une coloration k-frugale des sommets d'un graphe est une coloration propre (deux sommets adjacents ont des couleurs distinctes) telle que dans chaque voisinage, chaque couleur apparait au plus k fois. Par exemple une coloration 1-frugale d'un graphe G est exactement une coloration propre du carré de G. On s'intéresse à la coloration frugale des graphes planaires, ainsi qu'à la coloration frugale des arêtes des multigraphes. Ces problèmes sont reliés au L(p,q)-labelling, à la coloration du carré des graphes, et à la coloration cyclique des graphes planaires.

(travail en collaboration avec Omid Amini et Jan van den Heuvel)
 Plus d'infos  


2007-10-05Connectivité dans les graphes planaires
14:00-15:00
Salle 75
Dans cet exposé je présenterai la variante d'un problème d'étiquetage: l'étiquetage avec ensembles interdits. Il s'agit de calculer des étiquettes pour les sommets d'un graphe G de sorte que l'on puisse déterminer ensuite si les sommets x et y sont dans la même composante connexe du graphes GX, étant données les étiquettes des sommets x,y et celles de l'ensemble interdits X. Pour les graphes planaires, je montrerai que l'on peut résoudre ce problème avec des étiquettes de O(log|V(G)|) bits.

Travail joint avec: B. Courcelle, M. Kanté et A. Twigg
 Plus d'infos  


2007-09-28coloration orientée forte de graphes
14:00-15:00
Salle 75
Je commencerai par un résumé des résultats concernant la coloration orientée,
ainsi que la coloration orientée forte. Puis, je présenterai des résultats obtenus avec
Alexandre Pinlou et Pascal Ochem sur la famille des graphes planaires sans cycles de
longueurs données.
 Plus d'infos  


2007-09-07The Hull and Geodetic Numbers of Orientations of Graphs
14:00-15:00
Salle 75
For every pair of vertices u,v in an oriented graph, a u-v geodesic is a shortest directed path from u to v. For an oriented graph D, let I_{D}[u,v] denote the set of all vertices lying on a u-v geodesic or a v-u geodesic. And for Ssubseteq V(D), let I_{D}[S] denote the union of all I_{D}[u,v] for all u,vin S. If S is a convex set then I_{D}[S]=S. Let [S]_{D} denote the smallest convex set containing S. The geodetic number g(D) of an oriented graph D is the minimum cardinality of a set S with I_{D}[S]=V(D). The hull number h(D) of a digraph D is the minimum cardinality of a set S with [S]_{D}=V(D). For a connected graph G, let O(G) be the set of all orientations of G, define g^{-}(G)=min{ g(D):Din O(G)}, g^{+}(G)=max{ g(D):Din O(G)}, h^{-}(G)=min{ h(D):Din O(G)}, and h^{+}(G)=max{ h(D):Din O(G)}. By the definitions, h^-(G)le g^-(G) and h^+(G)le g^+(G). In the paper, we prove that g^-(G)< h^+(G) for graph G of order at least 3 and show that, for any nonnegative integers a and b, there exists a connected graph G such that g^-(G)-h^-(G)=a and g^+(G)- h^+(G)=b. These results answer all problems of Farrugia in [Discrete A. Math. 148 (2005) 256-262].
 Plus d'infos  


2007-06-15Circular flow on bidirected graphs
14:00-15:00
Salle 75
In this talk we will deal with circular flow number of signed graphs.
A conjecture of Bouchet is equivalent to the statement that every s-bridgeless signed
graph has circular flow number at most 6. We prove an analog of
the Hoffman flow theorem for signed graphs, and relates the circular flow
number of a signed graph G to the imbalance ratio of orientations of G.
Using this relation, we prove that any 6-edge connected s-bridgeless signed
graph has circular flow number strictly less than 4.
 Plus d'infos  


2007-06-08Schéma d'adjacence pour les graphes planaires
14:00-15:00
Salle 75
Un schéma d'adjacence d'un graphe est un codage du graphe distribué sur ses sommets. Le
principe est d'associer à chaque sommet du graphe de l'information sous la forme d'une
étiquette binaire de façon à ce que l'on puisse déterminer l'adjacence entre deux sommets
en examinant seulement leurs étiquettes. Je vous présenterais un tel schéma pour les
graphes planaires de n sommets avec des étiquettes de (2+o(1))log n bits. L'idée du
schéma est
d'utiliser un nouveau schéma avec de étiquettes de (1+o(1))log n bits pour les planaires
extérieurs et la décomposition des graphes planaires en deux graphes planaires
extérieurs. De la même manière, on étend ce résultat aux graphes excluant un mineur fixé
en utilisant un nouveau schéma pour les graphes d'arboricité bornée.
 Plus d'infos  


2007-05-25Deux résultats polonais sur les graphes arbitrairement décomposables
14:00-15:00
Salle 75
Une décomposition d = (d1, ..., dk) de n est une suite d'entiers positifs dont la somme égale n. Un graphe G=(V,E) avec |V| = n, est dit arbitrairement décomposable si pour toute décomposition d = (d1, ..., dk) de n, il admet une partition de V = (V1, ... Vk) telle que

1) pour tout i, |Vi| = di

2) pour tout i, le sous-graphe induit par Vi est connexe

Après un rappel des définitions et résultats déjà obtenus, je présenterai deux résultats dus à des collègues polonais. Le premier porte sur une condition sur les degrés qui garantit qu'un graphe soit arbitrairement décomposable, le second caractérise les arbres on-line arbitrairement décomposables, une sous-classe des arbres arbitrairement décomposables.
 Plus d'infos  


2007-05-11Dualité treewidth/bramble et fonctions partition sous-modulaires
14:00-15:00
Salle 75
En adaptant une méthode proposée par Robertson et Seymour, nous proposons une nouvelle preuve de la dualité entre le bramble-number d'un graphe et sa treewidth. Cette preuve repose sur des fonctions partition. Cette technique permet d'étendre la notion de dualité à d'autres paramètres classiques des graphes.
 Plus d'infos  


2007-05-04Graphes de cordes de maille au moins cinq
14:00-15:00
Salle 75
Les graphes de cordes sont les graphes d'intersection des cordes d'un cercle.
Dans cet exposé, on s'intéressera à la structure de ces graphes lorsqu'ils sont peu
denses. En particulier on regardera les configurations spécifiques qui apparaissent
lorsque la maille grandit, et on s'en servira pour donner une estimation précise de la
densité des graphes de cordes en fonction de leur maille (c'est très surprenant, on voit des racines carrées apparaître).
 Plus d'infos  


2007-04-20Les graphes planaires et leur modèle d'intersection de segments
14:00-15:00
Salle 075
Étant donné un graphe G et un ensemble S de segments du plan, S est un modèle de G s'il y a une bijection b entre V(G) et S telle que : uv est une arête de G ssi les segments b(u) et b(v) s'intersectent. Il existe des graphes n'ayant pas de tel modèle. Dans sa thèse Scheinerman a conjecturé que tout graphe planaire a un modèle. Différents travaux ont porté sur des familles restreintes de graphes planaires telles que les graphes planaires bipartis ou sans triangles. Dans cet exposé, nous présenterons une preuve de cette conjecture pour tous les graphes planaires. (en collaboration avec J.Chalopin)
 Plus d'infos  


2007-04-06The chromatic number of mixed paths
14:00-15:00
Salle 75
An (n,m)-mixed graph has vertices linked by arcs and edges; the arcs are colored with n colors, the edges are colored with m colors and the underlying graph is simple.
A homomorphism between two such graphs is a vertex map, such that the images of two vertices which are joined by an edge (resp. arc) are joined by an edge of the same color (resp. arc of the same color and orientation). The chromatic
number of an (n,m)-mixed graph G is then defined to be the smallest order of a homomorphic image of G.

It is known that every (n,m)-mixed tree has chromatic number at most 2n+m+2 for m>0 even, and 2n+m+1 for m odd or m=0. We show that these values can be attained by paths.
 Plus d'infos  


2007-03-30Cops and robbers : un survol
14:00-15:00
Salle 75
Les jeux de policiers de voleurs reviennent a la mode. Cet expose fera un survol de certains aspects de la problematique.

Cops-and-robbers game are coming back. This talk will give a survey of some aspects of the problems.
 Plus d'infos  


2007-03-23Real choosability of a graph
14:00-15:00
Salle 75
Le but de cet exposé est de présenter les origines de la 'real choosability', à savoir la T-coloration, introduite par Tesman, la T-choosability par Alon et Zaks, la coloration circulaire, version discrète et continue, enfin la coloration réelle par listes, version discrète, etudiée partiellement par Waters et la 'real choosability', version continue. Je présenterai brièvement l'application à la distribution de ressources avec contraintes temporelles. Je definirai ensuite le 't-choosability ratio' et le 'nombre chromatique réel'. On s'interessera particulièrement au '1-choosability ratio' et je donnerai les outils permettant de borner ce paramètre. Je finirai avec l'énoncé de problèmes dont l'étude permettrait de mieux comprendre ce nouveau paramètre.
 Plus d'infos  


2007-03-16Routage dans les graphes cellulaires
14:00-15:00
Salle 75
Il est établit depuis 2001 que tout arbre à n sommets possède un schéma de routage de plus courts chemins utilisant des adresses, des en-têtes et des tables de routage de O(log n) bits. Il est ouvert de savoir si ce résultat optimal peut être étendu à des graphes plus généraux. En particulier Fraigniaud et al. ont posé la question de savoir si ce résultat restait vrai pour les graphes planaires-extérieurs, une classe de graphes planaires contenant les arbres. Dans cet article, nous répondons positivement à cette question. En fait, nous étendons le résultat à des graphes valués beaucoup plus généraux, appelés k-cellulaires. Tout graphe est k-cellulaire pour une certaine valeur de k, mais ces graphes comprennent, par exemple, le cas des graphes planaires où tous les sommets peuvent être couverts par O(k) faces disjointes, et dans ce cas le schéma de routage peut être construit en temps quadratique.
 Plus d'infos  


2007-03-09Object Location Using Path Separators (PODC 2006)
14:00-15:00
Salle 075
Robertson et Seymour ont donné dans "Graph Minors
16, 2003" une caractérisation des graphes ne contenant pas un graphe
arbitraire H comme mineur. Cette caractérisation est basée sur une
décomposition arborescente très complexe des graphes. Basé sur cette
dernière, nous montrons que les graphes excluant un mineur sont
"k-chemins séparables" où k est une constante ne dépendant que du
mineur exclu. Grosso modo cela signifie que de tels graphes peuvent
être coupé en deux en supprimant au plus k plus courts chemins. La
propriété de k-chemin séparable a de nombreuses applications: routage,
oracle de distance, petits-monde, etc.

Dans cet exposé je me contenterai de donner les concepts de base
pour comprendre l'énoncé du théorème de décomposition de Robertson et
Seymour, ainsi que les idées principales permettant de montrer que les
graphes excluant un mineur sont k-chemins séparables.

(En collaboration avec Ittai Abraham, Université de Hébraique de Jérusalem)
 Plus d'infos  


2007-02-16Homomorphismes de graphes et complexité descriptive des problèmes de satisfaction de contraintes
14:00-15:00
Salle 75
Les problèmes de satisfaction de contraintes (CSPs) peuvent être modélisés en terme d'existence d'homomorphisme entre des structures relationnelles finies. Feder et Vardi ont introduit un fragment de la logique monadique du second ordre, MMSNP, et prouvent que la classe des problèmes capturés par cette logique est polynomialement équivalente à celle des CSPs. Cependant cette équivalence "à réduction polynomiale prêt" est contrastée par le fait que MMSNP capture des problèmes qui ne sont pas des CSPs (sur la même signature). De plus, Bodirsky et Dalmau ont montré que de nombreuses formules de MMSNP sont en fait des CSPs infinis. Dans cette exposé je vais m'intéresser en particulier à la question suivante: étant donné une formule de MMSNP, est-ce-que cette formule capture un CSP ou non? Cette question est lié à la notion de dualité (homomorphique) et sa généralisation de dualité d'ombre (shadow duality) étudié par Nesetril et. al. Je vais également m'intéresser à la question de complexité descriptive des CSPs infinis.
 Plus d'infos  


2007-02-09Mots de Gauss, parcours diagonaux (ou en zig zag)
14:00-15:00
Salle 75
Les mots de Gauss représentent les intersections avec elle même d'une
courbe fermée dans le plan.
Plusieurs courbes non homéomorphes peuvent
avoir le même mot de Gauss "à double occurrences".
On s'intéresse à caractériser toutes les courbes correspondant à un
mot donné.
Pour ce faire on reformule le problème en termes de
parcours en zig-zag de cartes planaires et de graphes "médiants" (medial graphs).
On montre que deux cartes planaires ont les mêmes parcours en zig-zag ssi
elles sont localement duales, notion nouvelle
introduite dans ce but.
Toutes ces constructions se formalisent sans peine en logique
du second-ordre monadique.
 Plus d'infos  


2007-01-26An adaptation of Eppstein’s algorithm
14:30-15:30
Salle 075
The speaker will present an adaptation of Eppstein’s algorithm building, for a
given directed graph, the K shortest circuitless paths having at most P
arcs between a source node and a target node.
 Plus d'infos  


2007-01-19Colorations circulaires des graphes sans griffes
14:00-15:00
075
(à venir)
 Plus d'infos  


2007-01-12Searching for black-hole faults in a network using multiple agents
14:00-15:00
Salle 178
We consider a fixed communication network where (software) agents can move freely from node to node along the edges. A "black hole" is a faulty or malicious node in the network such that if an agent enters this node, then it immediately "dies". We are interested in designing an efficient communication algorithm for the agents to identify all black holes. We assume that we have k agents starting from the same node s and knowing the topology of the whole network. The agents move through the network in synchronous steps and can communicate only when they meet in a node. At the end of the exploration of the network, at least one agent must survive and must know the exact locations of the black holes. If the network has n nodes and b black holes, then any exploration algorithm needs Omega(n/k + D_b) steps in the worst-case, where D_b is the worst case diameter of the network with at most b nodes deleted. We give a general algorithm which completes exploration in O((n/k)log n/loglog n + b D_b) steps for arbitrary networks, if b <= k/2. In the case when b <= k/2, bD_b=O(sqrt{n}) and k = O(sqrt{n}), we give a refined algorithm which completes exploration in asymptotically optimal O(n/k) steps. (joint work with Colin Cooper and Tomasz Radzik)
 Plus d'infos  


2006-12-15Graphes et jeux combinatoires
14:00-15:00
Salle 075
Cet exposé peut être vu comme une introduction, par un non spécialiste, au vaste et intriguant domaine des jeux combinatoires, complétée d'un certain nombre de questionnements relatifs notamment à divers jeux de coloration de graphes.
 Plus d'infos  


2006-12-08Circular colourings of hypergraphs
14:00-15:00
Salle 075
A generalization of the circular chromatic number to hypergraphs is discussed. In particular, it is indicated how the basic theory, and five equivalent formulations of the circular chromatic number of graphs, can be carried over to hypergraphs with essentially the same proofs.
 Plus d'infos  


2006-12-01Coloration orientée des graphes planaires sans cycles de longueurs données
14:00-15:00
Salle 075
Nous considérons la coloration orientée de la classe des
graphes planaires sans cycles de longueurs 4 à i. Nous obtenons, en
fonction de i, des bornes pour le nombre chromatique orienté de cette
classe de graphes. Certaines de ces bornes sont optimales.
 Plus d'infos  


2006-11-24Graphes universels et variantes
14:00-15:00
Salle 076
Cet exposé portera sur la notion de graphes universels ainsi que certaines variantes. Un graphe Fn-universel est un graphe contenant tous les graphes de la famille Fn de graphes de n sommets en tant que sous-graphe. Le but est bien sûr de minimiser le nombre d'arêtes du graphe. Il existe deux variantes connues pour ce problème: la variante induite qui impose que le graphe contienne les graphes de la famille en tant que sous-graphes induits et la variante orientée où l'on considère des graphes orientés. J'aborderai les résultats connus pour ces problèmes et notamment le cas des graphes de degré borné pour lequel nous améliorons les meilleures bornes précédemment connues.
 Plus d'infos  


2006-10-20Coloration de graphes et "méthode probabiliste"
14:00-15:00
Salle 75
Ce sera l'occasion de faire un rapide tour d'horizon de divers outils probabilistes (méthode du premier moment, bornes de concentration, Lemme Local,...) et de leur application en coloration de graphes. On montrera de manière très simple que les graphes sans triangles ont un nombre chromatique non borné, ainsi que certains résultats de coloration par listes des sommets et de coloration acyclique des arêtes d'un graphe.
 Plus d'infos  


2006-10-13Emergence distribuée des petit-mondes
14:00-15:00
075
Supposons qu'un réseau dispose d'un étiquetage de distances, cad chaque noeud est capable de calculer sa distance à tout autre noeud du réseau à partir d'un calcul sur les étiquettes des noeuds. Un réseau est un petit-monde s'il est possible d'effectuer un routage glouton avec un nombre logarithmique de sauts.
Les descriptions précédentes de réseaux petit-mondes navigables sont toutes centralisées. Pour le cas des graphes d'expansion borné, nous montrons comment les rendre petit-mondes de manière distribuée.
 Plus d'infos  


2006-10-06Graphes de grande maille appartenant à des classes closes par contraction d'arêtes.
14:00-15:00
Salle 075
Il est bien connu que les graphes planaires de maille 5k+1 contiennent un sommet de degré au plus 1 ou une chaine de k sommets de degrés 2. On montrera un lemme qui permet de retrouver ce genre de résultats. On obtient ainsi de nouveaux théorèmes de structure pour les 2-arbres partiels et les graphes circle (graphes d'intersection des cordes d'un cercle) de grande maille. La recherche de telles preuves d'existence de longues chaines de sommets de degrés 2 est motivée par des problèmes de coloration, notamment la coloration orientée des sommets ou des arcs. On terminera par des problèmes ouverts.
 Plus d'infos  


2006-09-29Sur la représentation en courbes des graphes planaires.
14:00-15:00
Salle076
Cet exposé portera sur la représentation des graphes planaires par des modèles d'intersections (travail effectué avec J. Chalopin et P. Ochem). Un graphe G=(V,E) est un "graphe courbe" si les éléments de V sont des courbes dans le plan et si les éléments de E sont les paires de courbes qui s'intersectent. On sait que tout graphe planaire est isomorphe à un graphe courbe. En effet, étant donnée une représentation planaire d'un graphe G il est possible de construire une "représentation en courbes" de G. Dans la representation en courbe classique d'un graphe planaire G, il est fréquent que deux courbes se croisent plusieurs fois. Dans cet exposé nous montrons que tout graphe planaire G admet un representation en courbes dans laquelle deux courbes se coupent au plus une fois.
 Plus d'infos  


2006-09-15Path routing problems in complete graphs.
14:00-15:00
Salle 075
The talk deals with certain routing problems consisting in the
assignment of paths to source-sink vertex pairs in an undirected
complete graph. The main topic of interest is the Maximum Edge-Disjoint
Paths problem, and we focus on a study of recent greedy and non-greedy
approximation algorithms, as well as of inapproximability results. Some
of the analyzed techniques can also be applied to solve the related
Congestion Routing and Wavelength Routing problems in complete graphs.
 Plus d'infos  


2006-09-08Circular chromatic index of graphs
14:00-15:00
Salle 075
Suppose $G$ is a graph and $p geq 2q$ are positive
integers. A $(p,q)$-coloring of $G$ is a mapping $f: V(G) o
{0,1,cdots,p-1}$ such that for every edge $xy$ of $G$, $q leq
|f(x) - f(y)| leq p-q$. The circular chromatic number $chi_c(G)$ of
$G$ is the minimum of the ratio $p/q$ for which there is a
$(p,q)$-coloring of $G$. It is known that for any graph $G$, we have
$chi(G)-1 < chi_c(G) leq chi(G)$ and hence $chi(G) = lceil
chi_c(G)
ceil$. The circular chromatic index of $G$ is defined to
be the circular chromatic number of the line graph of $G$. By Vizing
Theorem, any cubic graph has circular chromatic index at most $4$, and
the four color theorem is equivalent to say that any bridgeless cubic
planar graph $G$ has circular chromatic index $3$. In this talk, I
prove that any bridgeless cubic graph has circular chromatic index at
most $11/3$. The bound is best possible as the Petersen graph has
circular chromatic index $11/3$.
 Plus d'infos  


2006-06-30Coloration acyclique impropre (par listes)
14:00-15:00
Salle 075
On considère une coloration impropre des graphes, dans laquelle chaque classe de couleur a un degré max borné. On étudie la coloration acyclique impropre par listes de certaine classes de graphes et on montre par exemple que les graphes planaires extérieurs sont acycliquement (2,5)-choosable (i.e. 2-choosable avec des classes de couleur de degré max au plus 5) et que les graphes de degré max. 3 sont acycliquement (3,1)-choosable. On donne aussi un lien entre cette coloration et la conjecture de Borodin et al "les graphes planaires sont acycliquement 5-choosable".
 Plus d'infos  


2006-06-23Gathering in specific radio networks
14:00-15:00
Salle 075
We address the problem of gathering information into a central node of a radio network, where interference constraints are present. We take into account the fact that, when a node transmits, it produces interference in an area larger than the area in which its message can actually be received. The network is modeled by a graph; a node is able to transmit one unit of information to the set of vertices at distance at most $dt$ in the graph, but when doing so it generates interference that does not allow nodes at distance up to $di$ ($di >= dt$) to listen to other transmissions. Time is synchronous and divided into time-steps in each of which a round (set of non-interfering radio transmissions) is performed. Because this problem is hard to approximate in general graphs, we study *good* approximations in some specific topologies, like the path, balanced stars and the 2 dimensional grid. In all these cases we provide algorithms whose performance differs only by an additive constant from the theoretical minimum.
 Plus d'infos  


2006-06-16About the Minimum Energy Broadcasting in Wireless Ad Hoc Networks
14:00-15:00
Salle 075
The talk presents latest results mainly on the performance of the Minimum Spanning Tree (MST) heuristic for the Minimum Energy Broadcast Routing (MEBR) problem. The MEBR basically consists in throwing n wireless devices on a d-dimensional Euclidean space while setting one of them as the root. A node x transmitting with power energy P_x can reach a node y at distance |x,y| whenever P_x >= Beta |x,y|^alpha for suitable constants Beta and alpha. The goal is to perform the broadcast pattern of communication from the root while minimizing the total consumed energy. One of the most famous heuristic studied in the literature is definitely the MST one. It creates a minimum spanning tree from the fixed root over the complete directed weighted graph G obtained as follows.The wireless devices represent the nodes of G. Every two nodes x, y are connected by a directed edge with weight equal to Beta |x,y|^alpha. Visiting the obtained tree from the root, each node is assigned a power of transmission equal to the heavier outgoing edge. The problem will be discussed from both experimental and theoretical point of views.
 Plus d'infos  


2006-06-02Théorèmes de décomposition pour les graphes excluant un mineur.
14:00-15:00
Salle 075
Robertson et Seymour ont récemment donné (dans "Graph Minors 16, 2003") une caractérisation des graphes ne contenant pas un graphe arbitraire H comme mineur. Cette caractérisation est basée sur une décomposition arborescente très complexe des graphes. Basé sur cette dernière, nous montrons que les graphes excluant un mineur sont "k-chemins séparables" où k est une constante ne dépendant que du mineur exclu. Grosso modo cela signifie que de tels graphes peuvent être coupé en deux en supprimant au plus k plus courts chemins. La propriété de k-chemin séparable a de nombreuses applications: routage, oracle de distance, petits-monde, etc.

Dans cette exposé je me contenterai de donner les concepts de base pour comprendre l'énoncé du théorème de décomposition de Robertson et Seymour, ainsi que les idées principales permettant de montrer que les graphes excluant un mineur sont k-chemins séparables.

Mots-clés: décomposition arborescente, surface orientable, surface non-orientable, vortex, joint, torso, etc.
 Plus d'infos  


2006-05-19Graphes décomposables - Olivier Baudon.
14:00-15:00
Salle 075
Il s'agit de caractériser les graphes d'ordre n tels que pour toute décomposition de n en une somme de k entiers a1, ..., ak (a1 + a2 + ... ak = n), il existe une partition des sommets de G en k sous-ensembles A1, ... Ak tels que pour tout i |Ai| = ai et le sous-graphe induit par Ai est connexe. L'exposé présentera les résultats récents de Barth et Fournier sur les arbres et quelques questions ouvertes.
 Plus d'infos  


2006-04-28Mobile Agent Rendezvous in a Synchronous Torus - Euripides Markou.
14:00-15:00
Salle 075
We consider the rendezvous problem for identical mobile agents (i.e., running the same deterministic algorithm) with tokens in a synchronous torus with a sense of direction and show that there is a striking computational difference between one and more tokens. More specifically, we show that 1) two agents with a constant number of unmovable tokens, or with one movable token, each cannot rendezvous if they have o(log n) memory, while they can perform rendezvous with detection as long as they have one unmovable token and O(log n) memory; in contrast, 2) when two agents have two movable tokens each then rendezvous (respectively, rendezvous with detection) is possible with constant memory in an arbitrary n x m (respectively, n x n) torus; and finally, 3) two agents with three movable tokens each and constant memory can perform rendezvous with detection in a n x m torus.
 Plus d'infos  


2006-04-14Conception de réseaux embarqués tolérants aux pannes - Mickaël Montassier
14:00-15:00
Salle 075
La fiabilité des réseaux embarqués dans les satellites de télécommunication, maillons essentiels dans la chaîne de la diffusion d'information, est un enjeu important. Comment concevoir des réseaux embarqués à faible coût capables de tolérer un certain nombre de pannes et de continuer à propager l'information ? Nous donnons des éléments de réponse à cette problématique posée par Alcatel Space Industries en présentant des réseaux de coût minimum supportant un nombre de pannes donné.
 Plus d'infos  


2006-04-07A revival of the girth conjecture - Tomas Kaiser
14:00-15:00
Salle 075
It was conjectured by Jaeger and Swart that non-3-edge-colourable cubic
bridgeless graphs have bounded girth. Although this `Girth Conjecture' has been disproved, we show that its analogue for the circular edge-colouring `holds' in an asymptotic sense. This is joint work with Dan Kral, Riste Skrekovski and Xuding Zhu.

 Plus d'infos  


2006-03-31Classes de graphes définies par intersection et/ou par chevauchement - Pascal Ochem
14:00-15:00
Salle 075
On parlera de deux hiérarchies de classes de graphes, définies
respectivement par des intersections et des chevauchements d'objets connexes.
Certaines classes apparaissent dans les deux hiérarchies.
Par exemple, un graphe "circle" est le graphe d'intersection de cordes d'un
cercle, et c'est aussi graphe de chevauchement de sous-chemin d'un chemin.
Il y aura des résultats d'inclusions de classes de graphes, dont certain
découlent du résultat suivant: la classe "interval filament"
(définie par intersection) correspond à la classe des chevauchements
de sous-graphes d'un caterpillar.
C'est travail en commun avec Jérémie Chalopin et Daniel Gonçalves.
 Plus d'infos  


2006-03-24Extraction de sous-graphes tres denses dans un graphe de tres grande taille - Yon Dourisboure.
14:00-15:00
Salle 075
Etant donne un graphe, en extraire des sous-graphes tres denses, tels que les cliques ou les bibartis complets, est un probleme connu pour sa grande complexite algorithmique. C'est pourtant un probleme qui intervient notamment dans la recherche de communautes dans le graphe du web. Ce graphe, dont les sommets representent les pages web et les arcs representent les hyperliens entre les pages, possede a ce jour quelques milliards de sommets et dizaines de milliards d'arcs. Les algorithmes classiques sont donc inutilisables. Nous presenterons une heuristique permettant d'extraire de grands sous-graphes tres denses dans des graphes de tres grande taille. Pour l'instant, cette heuristique a ete testee sur des graphes ayant jusqu'a 40 Millions de sommets et 1 Milliards d'arcs, les resultats ont ete obenus en quelques minutes avec une machine a 1.4GHz ayant 1.5Go de memoire.
 Plus d'infos  


2006-03-17Étiquetage compact par parcours bondissant - Arnaud Labourel
14:00-15:00
Salle 075
Un étiquetage d'adjacence d'un famille F de graphes consiste en une fonction qui associe à chaque sommet des graphes de F une étiquette binaire, tel que l'on puisse calculer l'adjacence entre 2 sommets à partir de leurs étiquettes. Nous donnons une fonction d'étiquetage pour la famille des caterpillars et des arbres binaires d'au plus n sommets avec des étiquettes de taille au plus log n+O(1) bits grâce à une nouvelle méthode d'étiquetage nommée parcours bondissant
 Plus d'infos  


2006-03-03Colorations injectives - André Raspaud
14:00-15:00
Salle 075
Une coloration injective d'un graphe G=(V,E) est une coloration des sommets telle que deux sommets reliés par une chaîne de longueur 2 ont des couleurs différentes. Nous donnons de nouvelles bornes pour le nombre chromatique injectif d'un graphe.
 Plus d'infos  


2006-02-24Décomposition distribuée de graphe - Bilel Derbel
14:00-15:00
Salle 075
On s'interesse à un algorithme de décompostion de graphe permettant d'obtenir des clusteurs (ensembles de noeuds) avec un petit rayon et faiblement connectés entre eux. Plusieurs applications distribuées utilisent ce type de décompostion comme point de départ, d'ou l'importance de construire ce type de décomposition de facon efficace. Je présenterais un algorithme de décomposition complètement distribué ayant une complexité linéaire en temps. Ensuite, je présenterais un algorithme produisant la même décompositon en temps sous-linéaire. Enfin, je présente une application aux spanners (graphes couvrants peu denses).
 Plus d'infos  


2006-02-10Inégalites de familles de cliques (suite et fin) - Arnaud Pêcher
14:00-15:00
Salle 075
Les inégalités de familles de cliques forment une famille d'inégalités qui sont valides pour le polytope des stables d'un graphe (quelconque). Lors du précédent groupe de travail, nous avons vu comment majorer leur rang de Chvatal, mais je n'ai pas précisé l'intérêt de ces inégalités. Ce sera chose faite dans cette seconde partie!
 Plus d'infos  


2006-01-20Arnaud Pêcher - A propos du rang de Chvatal des inégalites de familles de cliques
14:00-14:00
075
Les inégalités de familles de cliques forment une famille d'inégalités
qui sont valides pour le polytope des stables d'un graphe (quelconque).
Gianpaolo Oriolo a écrit qu'elles ne résultaient pas de techniques
d'arrondi classiques, et de fait, la preuve publiée de leur validité est
assez ingénieuse.
Dans cet exposé, je vais expliquer comment obtenir une majoration du
rang de Chvatal de ces inégalités. Cette majoration donne une preuve
différente de leur validité, basée uniquement sur des techniques
élémentaires d'arrondi...
 Plus d'infos  




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


Date Heure de début Heure de fin Titre Résumé Lieu Actif Public Fréquence Plus d'infos
2006-01-13  14:00:00  15:00:00  GT Graphes et Applications  Nous aurons le plaisir d'écouter Olivier Beaumont. Il nous parlera des méthodes ellipsoides pour la programmation linéaire (en nombres rationnels) et de leurs applications à la construction d'algorithmes polynomiaux pour de nombreux problèmes (en particulier des problèmes de coloriage dans leur version fractionnaire).  075  actif  public  7 jours  Plus d'infos


Retour
Retour à l'index