2006-2007

15 juin 2007 - Circular flow on bidirected graphs - André Raspaud

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.

8 juin 2007 - Schéma d'adjacence pour les graphes planaires - Arnaud Labourel

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.

25 mai 2007 - Deux résultats polonais sur les graphes arbitrairement décomposables - Olivier Baudon

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.

11 mai 2007 - Dualité treewidth/bramble et fonctions partition sous-modulaires - Nicolas Nisse (LRI)

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.

4 mai 2007 - Graphes de cordes de maille au moins cinq - Louis Esperet

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).

20 Avril 2007 - Les graphes planaires et leur modèle d'intersection de segments - Daniel Gonçalves

é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)

6 Avril 2007 - The chromatic number of mixed paths - Amanda Montejano (Universitat Politècnica de Catalunya)

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.

30 Mars 2007 - Cops and robbers - un survol - Gena Hahn (Université de Montréal)

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.

23 Mars 2007 - Real choosability of a graph - Nicolas Roussel

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.

16 Mars 2007 - Routage dans les graphes cellulaires - Youssou Dieng

Il est établi 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.

9 Mars 2007 - Object Location Using Path Separators (PODC 2006) - Cyril Gavoille

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 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.

16 Février 2007 - Homomorphismes de graphes et complexité descriptive des problèmes de satisfaction de contraintes - Florent Madelaine (University of Durham, UK)

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.

9 Février 2007 - Mots de Gauss, parcours diagonaux (ou en zig zag) et dualité locales - Bruno Courcelle

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.

26 Janvier 2007 - 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 - Hervé Bricard (RENAULT / Direction des Technologies et des Systèmes d'Information)

Tout est dans le titre!

19 Janvier 2007 - Colorations circulaires des graphes sans griffes - Arnaud Pêcher

Lors de la venue de Xuding Zhu en septembre dernier, nous avons étudié les colorations circulaires des graphes sans griffes. Ainsi nous avons donné une caractérisation des graphes sans griffes circulaires-parfaits contenant un antitrou impair induit de taille au moins 7, et découvert une propriété structurelle de certains graphes quasi-adjoints. Dans cet exposé, je vais expliquer comment utiliser ces deux résultats pour donner * une preuve différente de celle de Chvatal et Sbihi du théorème fort des graphes parfaits pour les graphes sans griffes; * une preuve différente d'une borne très récente de Chudnovsy et Ovetsky sur le nombre chromatique des graphes quasi-adjoints.

12 Janvier 2007 - Searching for black-hole faults in a network using multiple agents - Ralf Klasing

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/\log\log 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)

15 Décembre 2006 - Graphes et jeux combinatoires - Eric Sopena

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.

8 Décembre 2006 - Circular colourings of hypergraphs - Gary McGillivray (University of Victoria, Canada)

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.

1er Décembre 2006 - Coloration orientée des graphes planaires sans cycles de longueurs données - Alexandre Pinlou

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.

24 Novembre 2006 - Graphes universels et variantes - Arnaud Labourel

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.

20 Octobre 2006 - Coloration de graphes et "méthode probabiliste" - Louis Esperet

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.

13 Octobre 2006 - Emergence distribuée des petit-mondes - Nicolas Hanusse

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ée, nous montrons comment les rendre petit-mondes de manière distribuée.

6 Octobre 2006 - Graphes de grande maille appartenant à des classes closes par contraction d'arêtes. - Pascal Ochem

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.

29 Septembre 2006 - Sur la représentation en courbes d'un graphe planaire. - Daniel Gonçalves

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.

15 Septembre 2006 - Path routing problems in complete graphs. - Adrian Kosowski (Dept. of Algorithms and System Modeling, Gdansk University of Technology, Poland)

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.

8 Septembre 2006 - Circular chromatic index of graphs. - Xuding Zhu

Suppose $G$ is a graph and p \geq 2q are positive integers. A (p,q)-coloring of G is a mapping f: V(G) \to \{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) \rceil. 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.