La 7ème rencontre STINT aura lieu du lundi 4 au mercredi 6 décembre 2017 à Sophia Antipolis.
Programme
Lundi 4 décembre:
12-14h : Accueil et déjeuner.
14h : Alantha Newman, Partitioning small induced subgraphs for graph coloring.
P_t-free graphs contain no induced k-cycles for k >= t+1. Therefore, one approach to color a P_t-free graph is to divide the vertices into (few) sets such that all the odd cycles (of length at most t) are partitioned, i.e. each set is bipartite. We present an approach to partition short induced cycles in 3-colorable graphs. Our approach is based on semidefinite programming, which is a useful algorithmic tool for graph partitioning. We focus on partitioning the 5-cycles and 3-cycles in 3-colorable, P_6-free graphs. It is already known how to 3-color 3-colorable P_6-free graphs, but we hope that these methods can be extended.
Joint work with Vladan Jovicic.
15h : Frédéric Havet, On the minimum size of an identifying code over all orientations of a graph. Slides
For a graph or digraph G, let id(G) be the minimum size of an identifying code of G if one exists, and id(G) = +∞ otherwise. For a graph G, let idor(G) be the minimum of id(D) over all orientations D of G. We give some lower and upper bounds on idor(G). In particular, we show that idor(G) ≤ 3id(G)/2 for every graph G. We also show that computing idor(G) is NP-hard, while deciding whether idor(G) ≤ |V (G)| − k is polynomial-time solvable for every fixed integer k.
Joint work with Nathann Cohen.
16h : Session de problèmes Report
Mardi 5 décembre:
9h30-10h30 : Matej Stehlik, Generalised Mycielski graphs and the Borsuk-Ulam theorem. Slides
11h-12h : Jean-Claude Bermond, Dynamique de formations de groupes dans les réseaux sociaux. Slides
dans son groupe (c’est à dire la taille du groupe moins 1). La partition initiale est formée de n groupes de 1 personne. On autorise les mouvements suivants appelés k-déviations. Dans une k-déviation
d’une partition vers une autre au plus k personnes quittent leur groupes respectifs pour rejoindre un autre groupe ou en créer un sous réserve que leur utilité augmente. Ainsi dans une 1- déviation une
personne quitte son groupe pour un groupe de taille supérieure ou égale. Une partition est k-stable s’il n’existe pas de k-déviation de cette partition vers une autre. Dans le cas où il n’y pas d’ennemies la partition stable est formé d’un unique groupe des n personnes.
Dans l’exposé on se limitera au cas des 1-déviations. On s’intéressera à la dynamique de convergence mesurée par le nombre de 1-déviations utilisées pour atteindre à partir de la partition initiale une partition stable. En particulier on montre que dans le cas où il n’y a pas d’ennemies, une séquence de 1-deviations correspond à une chaîne dans le treillis des partitions d’entiers. Utilisant un résultat de Greene
et Kleitman on détermine ainsi exactement la taille de plus longue séquence de 1-déviations menant de la partition initiale en n groupes de une personne à la partition formé d’un seul groupe de n personnes
(elle contient $ 0(n^{3/2}$ 1-déviations). Dans le cas d’un graphe de conflit de nombre de stabilité $\alpha$ au vu du résultat ci-dessus Guillaume conjecturait que la plus longue séquence était en $O(n
\sqrt{\alpha})$. On donne un contre exemple en montrant qu’il existe des graphes de conflit avec $\alpha = \Omega (\sqrt {n})$ pour lesquels la plus longue séquence est en $0(n \alpha)$.
12-14h: Déjeuner.
14h : Maria Macekova, 3-colorability of (claw,H)-free graphs. Slides
The 3-COLORABILITY problem is NP-complete in the class of claw-free graphs in general. In the talk we focus on the computational complexity of the problem in subclasses of claw-free graphs defined by forbidding additional subgraphs. We give a necessary condition for the polynomial-time solvability of the problem in such classes and present some new result.
15h : William Lochet, Immersion of transitive tournaments in digraphs with large minimum outdegree.
We prove the existence of a function g(k) such that every simple digraph with minimum outdegree greater than g(k) contains an immersion of the transitive tournament on k vertices.
This solves a conjecture of Devos, McDonald, Mohar and Scheide.
Mercredi 6 décembre:
9h30-10h30 : Patrice Ossona de Mendez, Sparsity and Beyond.
We review some recent progress in the study of structural properties of sparse graphs and sketch recent exciting developments on “structural sparsity”, allowing to generalize tools used for sparse graphs to dense low complexity graphs
11h-12h : Pierre Aboulker, A tigth Erdös-Posá function for wheel minors. Slides
Let W_t denote the wheel on t+1 vertices. We prove that for every integer t > 2 there is a constant c=c(t) such that for every integer k> 0 and every graph G, either G contains k vertex-disjoint subgraphs each containing W_t as minor, or there is a subset X of at most c k log k vertices such that G-X has no W_t minor. This is best possible, up to the value of c. We conjecture that the result remains true more generally if we replace W_t with any fixed planar graph H.
Joint work with Samuel Fiorini, Tony Huynh, Gwenaël Joret, Jean-Florent Raymond and Ignasi Sau.
12-14h: Déjeuner.
Liste des participants.
EHESS (Paris)
Patrice Ossona de Mendez
G-SCOP (Grenoble)
Pierre Aboulker
Maria Macekova
Frédéric Maffray
Alantha Newman
Matej Stehlik
LIP
Khang Le
Nam Le
William Lochet
Stéphan Thomassé
Coati
Julien Bensmail
Jean-Claude Bermond
Frédéric Havet
Fionn Mc Inerney
Nicolas Nisse
Stéphane Pérennes