Journées Combinatoire et Algorithmes du Littoral Méditerranéen (Montpellier 30-31 Mars 2020)

Les JCALMs sont reportées sine die

Les JCALM sont des journées durant lesquelles nous organisons un groupe de travail sur un thème donné en Combinatoire ou Algorithmique. L'édition de mars 2020 aura lieu au LIRMM (salle séminaire, Bât. 4, campus St-Priest, Montpellier) et portera sur le théorème suivant, et sur ses nombreuses et importantes implications.

Théorème (M. Pilipczuk et S. Siebertz, 2018)

Pour tout graphes planaire $G=(V,E)$ il existe un ensemble de plus courts chemins disjoints de $G$, $P_1,\ldots,P_k$, tels que en contractant ces chemins, le graphe obtenu est de treewidth au plus 8. De plus ceci se fait en temps $O(n^2)$.

Programme (non-définitif)

Lundi 30 Mars

14h Théorèmes structuraux : partitions des graphes planaires (ref : https://arxiv.org/pdf/1807.03683.pdf et https://arxiv.org/pdf/1904.04791.pdf)

15h15 $p$-Centered Coloring & SubGraph Isomorphism (ref : https://arxiv.org/pdf/1807.03683.pdf et https://arxiv.org/pdf/1907.04586.pdf)

16h45 Conséquences pour le Queue-Number (ref : https://arxiv.org/pdf/1904.04791.pdf)

Mardi 31 Mars

9h30 Planar Graphs Have Bounded Nonrepetitive Chromatic Number https://arxiv.org/pdf/1904.05269.pdf

10h45 $K$-Planar Graphs https://arxiv.org/pdf/1907.05168.pdf

12h00 Déjeuner

13h30 Shorter Labeling Schemes for Planar Graphs https://arxiv.org/abs/1908.03341