2013-2014
2013 - 2014
Vendredi 6 septembre 2013 - Total Domination in graphs - Michael Henning.
Résumé :
The total domination number \gamma_t(G) of a graph G is the minimum cardinality of a set S of vertices so that every vertex of G is adjacent to a vertex in S. In this talk, we survey recent results on total domination in graphs. For example, we show that if G is a graph with no K_3-component and with all vertices of G contained in a triangle, then the total domination number of G is at most its matching number. We discuss recent results on total domination in graphs obtained using transversals in hypergraphs. For example, letting $f(3) = 0.7 - 1/130$, $f(4) = 0.65 + 1/300$ and $f(5) = (18f(4) + f(3))/20 \approx 0.6226154$, we show that if G is a graph of order $n$ with $\delta(G) \ge 5$, then $\gamma_t(G) \le (1 - f(5))n \le 0.377385$. Let $\cG(n,p)$ be a random graph of $n$ vertices where each edge is chosen with probability $p$. We show that for every $0 < \epsilon' < \epsilon$ and $p = (1+\epsilon') \sqrt{\frac{1}{n}( 2\ln n )}$, almost every graph $G \in \cG(n,p)$ has diameter two and $\left( \frac{1}{2\sqrt{2}} - \epsilon \right) \sqrt{n \, \ln(n) } < \gamma(G) \leq \gt(G) < \left( \frac{1}{\sqrt{2}} + \epsilon \right) \sqrt{n \, \ln(n) }$. We also present results on total domination in hypergraphs.
Vendredi 13 septembre 2013 - Homomorphisms of signed graphs - Éric Sopena.
Résumé :
A signed graph $(G, \Sigma)$ is a graph $G$ together with an assignment of
signs $+$ and $-$ to all the edges of $G$ where $\Sigma$ stands for the set of negative
edges. Furthermore $(G, \Sigma_1)$ and $(G, \Sigma_2)$ are considered to be
equivalent if the symmetric difference of $\Sigma_1$ and $\Sigma_2$ is an edge cut of $G$.
Several notions of graph
theory, such as the theory of minors and the theory of nowhere-zero flows, have been
already extended to signed graphs.
In this talk, we will mainly discuss signed graph homomorphisms and signed
graph minors.
Capturing the notion of the graph homomorphism order, signed graph homomorphisms
provide room for extensions and strengthenings of many homomorphism and
coloring theories on graphs.
In particular,
we will reformulate Hadwiger's
conjecture in the language of homomorphism of signed graphs whose underlying
graph is bipartite, and show that while some stronger form of the conjecture
holds for small chromatic number, such strengthening of the conjecture would not
hold for large chromatic numbers.
Vendredi 20 septembre 2013 - Théorèmes de compacité et de dualité pour certains paramètres dans les graphes infinis - Frédéric Mazoit.
Résumé:
La littérature fourmille de résultat de compacité pour les graphes infinis. Un bon exemple de ces résultats est qu'un graphe infini est k-coloriable si et seulement si tous ses graphes finis le sont. Un autre exemple connu est que la largeur arborescente d'un graphe infini est <k si et seulement si c'est le cas pour tous ses sous-graphes finis.
Par ailleurs, il est aussi connu que la largeur arborescente d'un graphe fini est >=k si et seulement si il existe un "bramble" d'ordre >k. Il existe de nombreux résultats du même type (pour la largeur de branches, la largeur de chemin…) que nous avions rassemblé dans le cadre unificateur des "fonctions de partition faiblement sous-modulaire".
Dans cet exposé, je vais montrer comment généraliser le cadre précédent pour obtenir à la fois un résultat de compacité et un résultat de dualité pour un certain nombre de largeurs connues.
Vendredi 27 septembre 2013 - Propagation radius - Paul Dorbec.
Résumé : Au cours de cet exposé, nous présenterons la notion de rayon de propagation introduite récemment pour mesurer l'efficacité d'un ensemble dominant de puissance. Nous présenterons quelques résultats associés sur les graphes de Sierpinski, une famille fractale de graphes. Ces résultats sont dus à des travaux communs avec Sandi Klavzar.
Vendredi 04 octobre 2013 : Polyhedra associated with identifying codes - Silvia Bianchi.
Exposé spécial WP6 Codes, Cryptologie, Algorithmique Arithmétique, en salle 76
Résumé : The identifying code problem is a newly emerging search problem,
challenging both from a theoretical and a computational point of view,
even for special graphs like bipartite graphs.
Hence, a typical line of attack for this problem is to determine minimum
identifying codes of special graphs or to provide bounds for their size.
In this work we study the associated polyhedra and present some general results on their combinatorial structure. We demonstrate how the polyhedral approach can be applied to find minimum identifying codes for particular graphs. Also we describe facet defining inequalities for the identifying code polyhedron of some bipartite graphs and odd cycles. Finally, we discuss further lines of research in order to obtain other facet defining inequalities to be added to linear relaxations of the identifying code polyhedron, in order to obtain suitable cutting planes to be used in a B\&C framework.
Vendredi 18 octobre 2013 : Partition Graphs and characterization of designs by graph homomorphims - Brett Stevens.
Résumé : Software testing makes use of combinatorial designs called covering arrays. These arrays are a generalization of Latin Squares and orthogonal arrays. Idealy we look to use the smallest possible array for the given parameters, but this is a hard problem. We define a family of graphs, partition graphs, which give a full charatcerization of optimal covering arrays using homomorphisms. These graphs have interesting properties and many interesting open questions.
Vendredi 25 octobre 2013 : Graphes sur des surfaces et codes quantiques - Gilles Zémor.
Salle 76
Résumé : Les cycles d'un graphe définissent un code correcteur simple et décodable efficacement.
Les analogues quantiques d'un code des cycles d'un graphe sont constitués de la donnée simultanée
de deux codes des cycles, l'un associé à un graphe dessiné sur une surface, et l'autre associé à son
graphe dual.
Soumettre un code des cycles à un canal à effacements revient graphiquement à regarder des sous-graphes
aléatoires. On ne peut pas décoder si et seulement si le sous-graphe contient un cycle. Dans le cas quantique,
l'événement pertinent survient lorsque le sous-graphe contient un cycle non-homogue à zéro. L'étude de
ce phénomène permet d'obtenir une formule semi-explicite, permettant d'avoir des bornes supérieures non-triviales, sur
la probabilité critique de la percolation sur les pavages réguliers auto-duaux du plan hyperbolique.
Travail commun avec Nicolas Delfosse.
Vendredi 8 novembre 2013 - Jeu de domination et graphes no-minus - Gabriel Renault.
Résumé : Le jeu de domination est un jeu a deux joueurs dont le plateau est un graphe fini sur lequel les joueurs construisent un ensemble dominant. Les joueurs choisissent chacun leur tour un sommet qui domine au moins un nouveau sommet et l’ajoutent a l’ensemble. Le jeu se termine lorsque l’ensemble ainsi construit forme un ensemble dominant. Un des joueurs, Dominator, a pour but d’arriver a un ensemble le plus petit possible, alors que l’autre joueur, Staller, essaie d’en maximiser la taille. Le nombre de domination ludique, noté γ_g , est la taille de cet ensemble lorsque les deux joueurs jouent de façon optimale et que Dominator commence la partie. On note γ'_g le paramètre défini de la même manière en considérant que Staller commence la partie. On s’intéresse ici a une classe de graphes pour laquelle on a toujours γ_g ≤ γ'_g , qu’on appelle les graphes “no-minus”, et dont le comportement vis-à-vis du jeu de domination est plus prévisible que dans le cas général. En particulier, on montre que les graphes “tri-split” et les graphes “dually-chordal” sont des graphes “no-minus”.
13 au 15 novembre 2013 - Journées Graphes et Algorithmes, Orsay
Vendredi 22 novembre 2013 (14h) - Vertex distinguishing colorings of graphs - Mariusz Wozniak.
Résumé : Let us consider a proper coloring $f$ of edges in a simple
graph $G=(V,E)$. Such a coloring defines for each vertex $x\in V$
the palette of colors, {\em i.e.}, the set of colors of edges incident with $x$,
denoted by $S(x)$. Two vertices $x$ and $y$ are \emph{similar} if
$S(x)=S(y)$. The minimum number of colors required in a proper
coloring $f$ without two similar vertices is called the {\em vertex-distinguishing index},
and is denoted by ${\rm vdi} (G)$. The vertex-distinguishing index was introduced
and studied (as ``observability'' of a graph) by \v{C}ern\'{y}, Hor\v{n}\'{a}k and Sot\'{a}k and, independently, (as ``strong coloring") by Burris and Schelp.
In general, for some families of graphs, the
vertex-distinguishing index can be much greater than the maximum degree. For instance, consider
a vertex-distinguishing coloring of a cycle of length $n$ with $k$ colors.
Since each palette is of size two, and the number of all possible palettes cannot be smaller than $n$, we have
$ {k\choose 2} \ge n $.
Hence, ${\rm vdi} (C_n) \ge \sqrt{2n}$.
However, if we distinguish the vertices in another way, namely by sets of color walks starting from vertices, not just by their palettes, then the number of colors we need is very close to the chromatic index.
Some relationships to other `distinguishing' parameters will be discussed such as the {\em distinguishing chromatic index}, {\em i.e.}, the minimum number of colors in a proper edge-coloring preserved only by the identity automorphism.
Vendredi 22 novembre 2013 (15h15) - Maximal cliques in Paley graphs - Mate Matolcsi.
Exposé spécial WP6 Codes, Cryptologie, Algorithmique Arithmétique.
Résumé : For infinitely many primes p = 4k + 1 we give a slightly improved upper bound
for the maximal cardinality of a set B \subset Z_p such that the difference set B − B
contains only quadratic residues. Namely, instead of the ”trivial” bound |B| ≤ \sqrt{p}
we prove |B| ≤\sqrt{p} − 1, under suitable conditions on p. The new bound is valid for
approximately three quarters of the primes p = 4k + 1.
Joint result with C. Bachoc and I. Z. Ruzsa.
Vendredi 29 novembre 2013 - Jeux combinatoires dans les graphes - Soutenance de thèse de Gabriel Renault.
Résumé :
Dans cette thèse, nous étudions les jeux combinatoires sous différentes contraintes.
Un jeu combinatoire est un jeu à deux joueurs, sans hasard, avec information complète et fini acyclique.
Nous regardons des jeux impartiaux et partisans, dans les conventions normale et misère.
Nous parlerons aussi de résultats obtenus sur des univers de jeux plus abstraits.
Vendredi 6 décembre 2013 - Algorithmes de routage et réduction des coûts de communication - Soutenance de thèse de Christian Glacet.
Vendredi 13 décembre 2013 - Decomposing oriented graphs into six locally irregular subgraphs - Julien Bensmail.
Résumé :
An undirected graph G is locally irregular if every two of its adjacent vertices have distinct degrees. In case G is not locally irregular but there is a partition (E_1, E_2, ..., E_k) of E(G) such that E_i induces a locally irregular subgraph of G for every i in {1, 2, ..., k}, we say that G is decomposable into k locally irregular subgraphs. It was recently conjectured that every undirected graph should be decomposable into three locally irregular subgraphs, unless it belongs to a well-characterized set of indecomposable graphs. We here consider an oriented version of the same problem, where a locally irregular oriented graph is defined as an oriented graph whose adjacent vertices have distinct outdegrees. Similarly as for the undirected case, we suspect every oriented graph to be decomposable into three locally irregular subgraphs. Towards this conjecture, we prove that every oriented graph is decomposable into six locally irregular subgraphs. This result contrasts with the undirected case for which no such constant upper bound has been proved so far. We finally establish the NP-completeness of the problem of deciding whether an oriented graph is decomposable into two locally irregular subgraphs.
This is joint work with Gabriel Renault.
Vendredi 20 décembre 2013 - Sur la L1-réalisabilité des triangulations - Nicolas Bonichon.
exposé en salle 76
Résumé :
On dit qu’une triangulation T (carte planaire dont toutes les faces internes sont des triangles) est Delaunay réalisable s’il existe un nuage de points P tel que la triangulation de Delaunay associée à ce nuage de point est égale à T. Dans cet exposé nous nous intéressons à la Delaunay réalisabilité des triangulations pour la norme L1. Nous présenterons des conditions nécessaires puis des conditions suffisantes pour qu’une triangulation soit L1-Delaunay réalisable. Les résultats présentés font intervenir un représentant de la famille des objets comptés par Baxter.
Vendredi 10 janvier 2014 - Les configurations d'entiers sur les sommets d'un graphe et leurs rangs - Robert Cori.
Résumé :
Dans le modèle du tas de sable (et aussi du "chip firing game")
on suppose donné un graphe (non orienté) et une configuration initiale consistant en des jetons
attribués à ses sommets.
Une règle de transition entre configurations appelée éboulement
consiste pour un sommet ayant un nombre de jetons supérieur ou égal à son degré
à donner un jeton à chacun de ses voisins.
Baker et Norine (2007) ont généralisé ce modèle en supposant que le nombre de jetons
attribué à chaque sommet peut être positif ou négatif (dans ce cas le sommet a une dette).
Ils généralisent la règle d'éboulement en supprimant la condition d'avoir suffisamment de jetons
pour effectuer un éboulement. Une première question consiste à déterminer les configurations
qui peuvent aboutir par une suite d'éboulements à une absence de sommets endettés. Ils introduisent aussi
une notion plus sophistiquée qui est celle du rang d'une configuration.
Après avoir donné des propriétés du rang,
on montrera comment le calculer pour certaines familles de graphes.
Vendredi 17 janvier 2014 - Le jeu de domination est P-Space log-complet - Paul Dorbec.
Résumé : Dans cet exposé informel, nous (re-)découvrirons le jeu de domination et le paramètre associé, le nombre de domination ludique. Après avoir un peu présenté les avancées récentes sur le jeu, nous vériefierons une réduction du jeu (en espace logarithmique) vers un problème P-Space complet, montrant la complétude du jeu de domination. Il faut noter que, à ma connaissance, il n'existe pas encore de tel résultat pour la version classique du jeu de coloration et du nombre chromatique ludique.
Vendredi 24 janvier 2014 - Flips - Prosenjit Bose.
Résumé : We review results concerning edge flips in triangulations concentrating mainly on various aspects of the following question: Given two different triangulations of the same size, how many edge flips are necessary and sufficient to transform one triangulation into the other? We focus both on the combinatorial perspective (where only a combinatorial embedding of the graph is specified) and the geometric perspective (where the graph is embedded in the plane, vertices are points and edges are straight-line segments). We highlight some of the techniques used to prove the main results and mention a few of the challenges remaining in this area.
Vendredi 31 janvier 2014 - Soutenance de thèse - Ahmed Wade.
"Complexité de l'exploration par agent mobile des graphes dynamiques"
Mardi 4 février 2014 - Soutenance de thèse - Sagnik Sen.
"A contribution to the theory of graph homomorphisms and colorings"
Vendredi 7 février 2014 - Mise à jour locale de graphes aléatoires - Romaric Duvignau.
Résumé : Les graphes k-sortants sont des graphes orientés dont chaque sommet possède exactement k voisins sortants. Nous étudions le problème de maintenir la distribution uniforme sur ces graphes lors d'une séquence arbitraire d'insertions et de suppressions de sommets. Le but étant de modéliser l'évolution de réseaux logiques dynamiques, nous nous plaçons dans un modèle local où nous n'avons pas accès à l'ensemble des sommets. Nous supposons à la place l'accès à une primitive globale renvoyant un sommet aléatoire uniforme du graphe. Nous présenterons dans cet exposé plusieurs algorithmes d'insertion et de suppression pour le problème de maintenance, dont les plus efficaces sont asymptotiquement optimaux.
Vendredi 14 février 2014 - Une introduction au calcul quantique tolerant aux fautes - Nicolas Delfosse.
Exposé spécial WP6 Codes, Cryptologie, Algorithmique Arithmétique.
Résumé : Alors que les composants classiques sont suffisamment fiables, chaque manipulation d'un bit quantique a une probabilité non négligeable d'introduire une erreur. Ceci rend l'application d'une porte quantique délicate. Je présenterai différentes techniques permettant de transformer un circuit quantique en un circuit quantique tolérant aux fautes.
Vendredi 21 février 2014 - Jeu de coloration - Clément Charpentier.
Résumé : Dans le jeu de coloration sur un graphe G, Alice et Bob colorent proprement, tour à tour, un sommet non coloré de G, construisant ainsi une coloration propre partielle de G de taille croissante. Alice gagne si, avec l'ensemble de couleurs disponibles, elle parvient à terminer la coloration. Bob gagne s'il réussit à rendre la coloration du graphe impossible.
Ce problème est étudié depuis un peu plus de 20 ans : dans cet exposé, nous reviendrons sur les principaux résultats, les stratégies les plus efficaces et les plus utilisées, les méthodes de preuve les plus courantes et les conjectures les plus motivantes. Et, peut-être, on présentera quelques résultats.
Vendredi 7 mars 2014 - Planar graphs with minimum cycle length at least 5 are (3,5)-colorable - André Raspaud.
Résumé : A graph is (d_1,...., d_r)-colorable if its vertex set can be partitioned into r sets V_1,......, V_r where the maximum degree of the graph induced by V_i is at most
d_i for each i in {1,... r}.
Let G_g denote the class of planar graphs with minimum cycle length at least g.
We focus on graphs in G_5 since for any d_1 and d_2, Montassier and Ochem constructed graphs in G_4 that are not (d_1, d_2)-colorable.
It is known that graphs in G_5 are (2, 6)-colorable and (4, 4)-colorable, but not (3, 1)-colorable.
We prove that graphs in G_5 are (3, 5)-colorable, leaving two interesting questions open: (1) are graphs in G_5 also (3, d_2)-colorable for some d_2 in {2, 3, 4}? (2) are graphs in G_5 indeed (d_1, d_2)-colorable for all d_1+d_2=8 where d_2>= d_1 >=1?
Vendredi 14 mars 2014 - Variants of edge-colouring - Petru Valicov.
Résumé : A strong edge-colouring of a graph is a partition of its edge-set into induced matchings. It is known that planar graphs can be strongly edge-coloured with 4Delta+4 colours, where Delta is the maximum degree of the graph. We improve this bound for several subfamilies of planar graphs and discuss some interesting links to a long standing conjecture of Vizing on proper edge-colouring of planar graphs. In the last part of the talk we will discuss a natural generalization of these two types of colourings where for two adjacent vertices the sets of colours incident to their edges have an intersection of bounded size. This last problem is related to some problems in combinatorial set theory. This is joint work with two groups of authors: J. Bensmail, A. Harutyunyan, H. Hocquard and V. Borozan, N. Cohen, J.C. Chang, N. Narayanan, R. Naserasr.
Mercredi 19 mars 2014 - Colorations, jeux et marquages dans les graphes - Soutenance de thèse de Clément Charpentier. Amphi du LaBRI à 14h30.
Résumé : Nous étudions plusieurs problèmes de coloration dans les graphes, pour certains avec une composante ludique, et les liens entre ces notions et des notions de marquage (i.e. d'ordres sur les sommets).
La coloration à distance 2 d'un graphe est une coloration de ses sommets telle que deux sommets à distance au plus 2 ont des couleurs différentes. Le L(p,q)-étiquetage est une généralisation de ce problème où les contraintes à distance 1 et 2 sont différentes. Nous donnons des résultats pour ces deux problèmes dans plusieurs classes de graphes peu denses (ayant un faible degré moyen maximum).
Le jeu de coloration sur un graphe est un jeu où deux joueurs, Alice et Bob, colorent tour à tour un des sommets non colorés d'un graphe, construisant ainsi une coloration propre partielle de plus en plus étendue de ce graphe. Alice tente d'étendre la coloration à l'ensemble du graphe, et Bob tente de l'en empêcher. Nous travaillons sur un invariant de graphe, le degré minmax, dont l'étude permet de déduire des résultats pour le jeu de coloration, et nous travaillons sur le jeu de coloration d'incidences, un cas particulier du jeu de coloration dans les graphes d'incidences.
Vendredi 21 mars 2014 - Méthode de compression d'entropie et applications - Mickaël Montassier.
Résumé : Nous essaierons de décrire une méthode générale basée sur la méthode de compression d'entropie permettant d'obtenir de nouveaux majorants sur des invariants de graphes tels que le nombre chromatique acyclique, le nombre de Thue, ...
Vendredi 28 mars 2014 - Graphe couvrant planaire de degré borné - Nicolas Bonichon.
Résumé :This talk considers the question: « What is the smallest maximum degree that can be achieved for a plane spanner of a complete Euclidean graph? » Without the planarity constraint, it is known that the answer is 3 which is also the best known lower bound on the degree of any plane spanner. With the planarity requirement, the best known upper bound on the maximum degree is 6, the last in a long sequence of results improving the upper bound. In this talk we show that the complete Euclidean graph always contains a plane spanner of maximum degree 4.
Vendredi 4 avril 2014 - Tout ce que vous n'avez jamais voulu savoir sur les meilleurs ordres - Frédéric Mazoit.
Résumé : De temps en temps, on tombe sur une définition mathématique et on se demande quel est l'esprit pervers qui a bien pu pondre cette « chose ». C'est la réaction que j'ai eue quand j'ai vu la définition de meilleur ordre. Mais comme je dois être un peu pervers moi aussi, j'ai voulu comprendre cette définition. Et comme souvent, en découvrant le contexte et les motivations de cette définition, tout s'éclaire. Dans cet exposé, je présenterai certains résultats liés à la théorie des ordres et pourquoi la notion de meilleur ordre est naturelle.
Vendredi 11 avril 2014 - Détection des roues dans les graphes - Emilie Diot.
Résumé : Les configurations de Truemper que sont les pyramides, les
theta-graphes, les prismes et les roues permettent de définir une famille
de graphes les excluant en tant que sous-graphes induits : les "universally
signable graphs". Je présenterais lors de ce GT des résultats de
complexités sur la détection de ces sous-graphes, et plus précisemment
celui sur la détection de la roue.
Vendredi 18 avril 2014 - Largeur de rang des graphes dénombrables. Définitions et compacité - Bruno Courcelle.
Résumé : La largeur de rang d'un graphe G, notée rwd(G), (en anglais rank-width) a été introduite par Oum et Seymour
dans un but algorithmique, notamment la construction d'algorithmes FPT.
On peut souhaiter étendre cette notion aux graphes infinis, et viser la "compacité" :
rwd(G) = borne supérieure des rwd(H) pour H sous graphe induit fini de G.
La définition la plus naturelle donne "seulement" que la largeur est au plus 2 fois la borne supérieure considérée ci-dessus.
En utilisant une notion d'arbre différente (quasi-arbre), qui autorise une infinité de noeuds sur le chemin entre 2 noeuds, on obtient la compacité exacte. Cette notion est définie en logique du premier ordre.
On regardera aussi dans cette perspective la largeur de rang linéaire, où l'arbre de décomposition est un ordre total sur les sommets du graphe.
Vendredi 23 mai 2014 - Hamilton Cycles in Colour Graphs - Gary MacGillivray.
Résumé : We will consider the problem of listing all colourings of a graph so that consecutive colourings in the list differ at exactly one vertex.
Vendredi 6 juin 2014 - 2-distance coloring of not-so-sparse graphs - Clément Charpentier.
Résumé : The 2-distance coloring of a graph G is a proper coloring of G where
every pair of vertices sharing a common neighbor
receives different colors.
The "maximum average degree" or "mad" of a graph is the maximum among
the average degrees of its subgraphs.
This is a way to evaluate the density (or the sparseness) of a graph,
both globally and locally.
Several results exist about the lesser number of colors needed for
2-distance coloring of graphs with bounded mad.
However, in all these results, the bound is strictly less than 4.
We present upper and lower bounds for the "2-distance chromatic
number" of graphs with mad bounded by 2k for every k.
Mardi 10 juin 2014 - Soutenance de thèse - Julien Bensmail - Partitions and decompositions of graphs.
Résumé : This thesis is dedicated to the study of two graph partition problems, namely the problems of partitioning a graph into connected subgraphs, and of distinguishing the adjacent vertices of a graph by means of an edge-weighting. Each of these two problems is studied regarding both the structural and algorithmic aspects.
Vendredi 13 juin 2014 - Constructing generalized Sudokus - Melissa Huggan.
Salle 178 à 13h30.
Résumé : Mathematical structure behind the world famous Sudoku puzzle is abundant. Using linear
algebra and coding theory, it is possible to build Sudokus and special Sudoku squares with additional
constraints and symmetries (symmetric Sudokus). We examine these beautiful constructions and use
them to generalize the notion of Sudoku to higher dimensional structures. Borrowing ideas from
varying areas of mathematics, we define and construct a variant on the hypercube which we call a
hyperSudoku.
Vendredi 13 juin 2014 - Soutenance de thèse - Dominik Pajak - Algorithms for Deterministic Parallel Graph Exploration.
Résumé : In this thesis we study the problem of parallel graph exploration using multiple synchronized mobile agents. Each mobile agent is an entity that can, independently of other agents, visit vertices of the graph and traverse its edges. The goal of the agents is to visit all vertices of the graph. We will study three different variants of the problem: (i) Exploration with agents equipped with memory that are allowed to communicate with each other. (ii) Exploration in the rotor-router model which can be seen as derandomization of the random walk. (iii) Collision-free exploration where each agent has to visit all nodes of the graph without meeting other agents.
Vendredi 20 juin 2014 - Incidence coloring of graphs with high maximum average degree - André Raspaud.
Résumé : An incidence of an undirected graph G is a pair (v,e) where v is a vertex of G and e an edge of G incident to v. Two incidences (v,e) and (w,f) are adjacent if one of the following holds: (i) v = w, (ii) e = f or (iii) vw = e or f. An incidence coloring of G assigns a color to each incidence of G in such a way that adjacent incidences get distinct colors.
In this talk we present bounds for incidence chromatic number of graphs having high maximum average degree. In particular we prove that every graph with maximum degree at least 7 and with maximum average degree strictly less than 4 admits a (Delta+3)-incidence coloring. This result implies that every triangle free planar graph with maximum degree at least 7 is (Delta+3)-incidence colorable.
Du lundi 30 juin au vendredi 4 juillet - ICGT 2014, Grenoble.
Vendredi 4 juillet 2014 - Codes séparateurs et surveillance de trafic - Thomas Bellitto.
Exposé spécial CPU/Axe 3
Résumé : Cette présentation porte sur les problèmes de séparation dont un exemple bien étudié au Labri est celui de code identifiant dans un graphe. Dans le cas général, il s'agit de trouver un ensemble de propriétés aussi petit que possible permettant de distinguer un ensemble d'individus donné. Nous étudierons des modèles basés sur différentes structures combinatoires et comparerons leur expressivité. Nous nous intéresserons ensuite au problème de surveillance de trafic dans un réseau qui consiste à déterminer où placer des capteurs sur les arcs d'un graphe pour pouvoir reconstituer le chemin suivi par un marcheur. Nous exprimerons ce problème comme un problème de séparation en introduisant un nouveau modèle : la séparation sur un langage. Nous étudierons ensuite ce nouveau problème et développerons des algorithmes de résolution, particulièrement sur les instances spécifiques issues du problème de surveillance de trafic.
Vendredi 11 juillet 2014 - Coloration distribuée et probabiliste - Akka Zemmari.
Exposé spécial CPU/Axe 3
Résumé : La coloration est un problème classique de la théorie des graphes et de l'algorithmique distribuée.
Dans cet exposé, je ferai un résumé des résultats obtenus récemment pour la résolution de ce problème. On montrera comment obtenir une (Delta+1)-coloration en O(log n) rondes et en utilisant des messages à 1 bit. Nous montrerons que l'algorithme est optimal et ce en utilisant des revêtements de graphes. Dans le cas où le réseau est un anneau, nous verrons qu'en utilisant la transformée de Mellin, il est possible de donner la valeur exacte de la constante cachée dans le O(log n).