2009-2010
2009 - 2010
Vendredi 18 septembre 2009 - Colorations Quasi-propres - Mickael Montassier.
Résumé : 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.
Vendredi 25 septembre 2009 - Colorations Quasi-propres, 2ème partie - Mickael Montassier.
Vendredi 2 octobre 2009 - Coloration acyclique - Hervé Hocquard.
Résumé : 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…
Vendredi 9 octobre 2009 - Homomorphism of planar graphs - Resa Naserasr.
Résumé : 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.
Vendredi 16 octobre 2009 - Euler tour lock-in problem in the rotor-router model - David Ilcinkas.
Résumé : (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.
Vendredi 13 novembre 2009 -Distance-two and incidence colorings of toroidal grids - Éric Sopena.
Résumé : (joint work with Jiaojiao Wu) 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.
Vendredi 20 novembre 2009 - Topological representations of planar partial cubes - Matjas Kovse.
Résumé : 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.
Vendredi 4 décembre 2009 - Spanner géométrique planaire de degré au plus 6 - Nicolas Bonichon.
Résumé : 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ć.)
Vendredi 11 décembre 2009 - Sur le nombre chromatique ludique des chenilles - Adrien Guignard.
Résumé : 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.
Vendredi 18 décembre 2009 - Comment se rencontrer de manière asynchrone dans un graphe quelconque - Arnaud Labourel.
Résumé : Dans cet exposé, je montrerais comment deux agents mobiles peuvent se rencontrer dans un graphe quelconque et possiblement infini. Le graphe est inconnu des agents et ses sommets sont anonymes. À chaque étape, l'agent doit choisir un numéro de port correspondant à une des arêtes incidentes du sommet courant et traverser cette arête. Les deux agents se rencontrent s'ils sont sur un même sommet ou s'ils se croisent sur une arête. On considère le modèle asynchrone. C'est-à-dire que la durée de chaque étape d'un agent est déterminée par un adversaire omniscient qui essaye d'empêcher le rendez-vous. Les agents ont des identifiants uniques afin de permettre le rendez-vous de manière déterministe. En effet, sans identifiants, deux agents déterministes auraient le même comportement et ne se rencontreraient jamais dans un cycle.
Je montrerais que le rendez-vous est toujours possible dans les graphes sous ces conditions et comment étendre ce résultat au rendez-vous d'agents mobiles dans le plan.
Vendredi 8 janvier 2010 - Coloration étoilée, partie 1 - André Raspaud.
Vendredi 15 janvier 2010 - Bipartite subgraphs of triangle-free subcubic graphs - Xuding Zhu.
Vendredi 29 janvier 2010 - Coloration étoilée, partie 2 - Min Chen.
Résumé : 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.]
Vendredi 5 fevrier 2010 - Domination de puissance - Paul Dorbec.
Résumé : La domination de puissance dans les graphes correspond à un problème de surveillance de l'état d'un réseau éléctrique à 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 rappelerons les résultats existants ainsi que quelques preuves originales.
Vendredi 12 fevrier 2010 - Décomposition de graphes et applications au jeu de marquage - Mickael Montassier.
Résumé : Soit k un entier positif. Nous montrerons que tout graphe de degré moyen maximum inférieur à 4(k+1)(k+3)/(k^2+6k+6) admet une partition des arêtes en une forêt et un sous-graphe de degré maximum au plus k. La preuve de ce résultat fera intervenir une méthode de déchargement à caractère global.
Vendredi 19 février 2010 - Codes et graphes extenseurs - Gilles Zémor (IMB).
Résumé : Les graphes extenseurs (expander graphs) sont des familles de graphes pour lesquels
tout sous-ensemble de sommets X su ffisamment 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).
Vendredi 26 février 2010 - Introduction to eigenvalue methods in graph theory - Reza Naserasr
Abstract: 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.
Vendredi 5 mars 2010 - Alon-Sack-Seymour Conjecture - Reza Naserasr
Abstract: 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.
Vendredi 12 mars 2010 - Interval graphs and packing problem - Petru Valicov
Résumé : 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.
Vendredi 19 mars 2010 • Some variations of identifying codes • Olivier Delmas
Résumé / Abstract: Identifying codes have been introduced in 1998 by M.G. Karpovsky and K. Chakrabarty and L.B. Levitin to model fault-detection in multiprocessor systems. In this talk, we introduce two variations of identifying codes: weak codes and light codes. They correspond to fault-detection by successive rounds. We'll explain difference between these variations, and we'll give some bounds and some examples on family of cycles.
Vendredi 26 mars 2010 - The hidden matching-structure of the composition of strips - Gautier Stauffer
Résumé : 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.
Vendredi 2 avril 2010 - Problems from the cold - Laurent Beaudou.
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.
Vendredi 9 avril 2010 - NP-complétude pour les colorations impropre, orientée et acyclique - Pascal Ochem (LRI).
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.
Vendredi 16 avril 2010 - Extremal cardinalities of identifying codes - Florent Foucaud.
Résumé : 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.
Vendredi 23 avril 2010 - Chemin séparabilité - Emilie Diot.
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.
Vendredi 7 mai 2010 - Bin Packing avec Contrainte de Distance - Hubert Larchevêque.
Résumé : 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é.
Vendredi 28 mai 2010 - The doubly-critical graph conjecture - Tomas Kaiser (Department of Mathematics, Plzeň University, Czech Republic).
Abstract: 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.
Vendredi 4 juin 2010 à 15h - On packing of graphs, digraphs and hypergraphs - Monika Pilsniak (AGH Cracovie)
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.
Mardi 8 juin 2010 à 10:00 - A linear time algorithm for L(2,1)-labeling of trees - Hirotaka Ono (Department of Informatics, Kyushu University, Japan)
Abstract: 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)|>= 2 if x and y are adjacent and |f(x)-f(y)|>= 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)->{0,...,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 O(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.
Vendredi 18 juin 2010 - Posets, Dependent Arcs, and Colorings - Lida Tong (Department of Mathematics, National Sun Yat-sen University, Kaoshiung, Taiwan).
Abstract : 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.
Vendredi 25 juin 2010 - Autour du théorème de caractérisation des graphes sans mineur H - Frédéric Mazoit
Résumé : 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.