2007-2008
20 juin 2008 - Compositions de jeux combinatoires : le jeu de domination sur les chemins - Éric Sopena
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.
13 juin 2008 - Dualité de certains paramètres de largeur de graphes (à la recherche de LA preuve...) - Frédéric Mazoit
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.
6 juin 2008 - Nowhere-zero flows in Cayley graphs - Martin Skoviera (Bratislava - Slovaquie)
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.
23 mai 2008 - On (1,2) Conjecture - Mariusz Wozniak (Cracovie - Pologne)
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?
18 avril 2008 - Nouvelles perspectives sur le problème de 3-coloration - Mickaël Montassier
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].
11 avril 2008 - Polytope des cliques circulaires et calcul du nombre d'indépendance des graphes sans griffe - Arnaud Pêcher
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.
4 avril 2008 - Routage dans les "arbres de graphes planaires-extérieurs de genre-r" - Youssou Dieng
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.
28 mars 2008 - Empilements et recouvrements dans les graphes - Paul Dorbec (Oxford, UK)
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.
21 mars 2008 - Permutations de Baxter et orientations bipolaires planes - Nicolas Bonichon
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.
14 mars 2008 - Représentation distribuée de distances dans les graphes - Arnaud Labourel
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.
7 mars 2008 - Etiquetage de propriétés du premier ordre dans des graphes de largeur de clique non bornée (suite) - Mamadou Kante
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).
15 Février 2008 - Hypohamiltonian cubic graphs of girth 7 - Edita Máčajová (Université Comenius, Bratislava, Slovaquie)
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.
8 Février 2008 - Beau quasi-ordre de fonctions de re-étiquetage - Michaël Rao (LIRMM, Montpellier)
Un pré-ordre (Q,<=) est "Well-quasi-ordered" (WQO) 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é.)
1er Février 2008 - Etiquetage de propriétés du premier ordre dans des graphes de largeur de clique non bornée - Mamadou Kante
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).
25 Janvier 2008 - Coloration adaptable des graphes planaires - Louis Esperet
É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.
18 Janvier 2008 - Graphes de démonstration, cographes et couplages parfaits - Christian Retoré
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.
11 Janvier 2008 - Colorations orientées des graphes planaires - Alexandre Pinlou (LIRMM, Montpellier)
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.
14 décembre 2007 - Une relaxation du problème de Havel - Mickaël Montassier
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.
7 décembre 2007 - On the growth rate of minor-closed classes of graphs - Olivier Bernardi (LRI)
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
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.
30 novembre 2007 - Jeux combinatoires sur les graphes (suite) - Adrien Guignard
23 novembre 2007 - Jeux combinatoires sur les graphes - Adrien Guignard
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.
16 novembre 2007 - On the hardness of constructing minimal 2-connected spanning subgraphs in complete graphs with sharpened triangle inequality. - Ralf Klasing
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).
23 octobre 2007 - Counting planar graphs and directed cycle double covers by matrix integrals - Martin Loebl (Charles University, Prague)
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.
12 octobre 2007 - Coloration frugale des graphes - Louis Esperet
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)
5 octobre 2007 - Connectivité dans les graphes planaires - Cyril Gavoille
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 G\X, é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
28 septembre 2007 - Coloration orientée forte de graphes - Mickaël Montassier
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.
7 septembre 2007 - The Hull and Geodetic Numbers of Orientations of Graphs - Li-Da Tong (National Sun Yat-sen University, Taiwan)
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 S\subseteq V(D), let I_{D}[S] denote the union of all I_{D}[u,v] for all u,v\in 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):D\in O(G)}, g^}(G)=max{ g(D):D\in O(G)}, h^{(G)=min{ h(D):D\in O(G)}, and h^{(G)=max{ h(D):D\in 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].