Journées Combinatoire Graphes Algo

10 et 11 décembre 2018
ENS Lyon

À l'occasion des 50 ans de Stéphan Thomassé

Programme (attention : les amphis changent selon les créneaux !) :

Lundi 10 décembre :

9h45 AMPHI E Accueil café
10h15 AMPHI E Stéphane Bessy : "Out-colouring of tournaments"
11h AMPHI E Nicolas Bousquet : "Frozen Delta+1 colorings of Delta-regular graphs."
     
11h30 cafétéria repas
... salles LIP groupes de travail
     
15h30 AMPHI B Louis Esperet : "Coloration distribuée avec un nombre optimal de couleurs"
16h15 AMPHI B Frédéric Havet : "Arbre dans les tournois"
     
19h45   Repas au restaurant Les Adrets (30 Rue du Bœuf, 69005 Lyon)

 

Mardi 11 décembre :

9h salle 313 Sud Accueil café
... salles LIP groupes de travail
     
11h30 cafétéria repas
     
13h15 AMPHI B Gwenaël Joret : "Large independent sets in triangle-free subcubic graphs"
14h00 AMPHI B Lucas Pastor : "Anciens et nouveaux résultats de coloration"
14h45 AMPHI B Aurélie Lagoutte : "Programmation dynamique et formulations étendues"

 

Pour se rendre à l'amphi E : 2 solutions :
     - demandez à l'accueil de l'ENS. Ils vous demanderont alors votre carte d'identité en échange d'un badge visiteur
     - dirigez-vous directement au rez-de-chaussée de la partie Nord du batiment. Avancez tout droit jusqu'aux premiers amphis, puis tournez à gauche. L'amphi E est au bout du couloir (vous monterez un demi-étage entre temps)

Pour les groupes de travail, les salles suivantes seront disponibles :
     - 313 Sud (salle de réunion de l'équipe, en face du bureau de Stéphan)
     - 316 Centre (à côté du coin café)
     - M7 3ème étage
     - M7 2ème étage
     - Bureaux MC2

 

Résumés des exposés :

Stéphane Bessy : Out-colouring of tournaments

We study vertex colourings of digraphs so that no out-neighbourhood is monochromatic and call such a colouring an out-colouring. Our main results are on tournaments and semicomplete digraphs. We prove that, except for the Paley tournament P7 , every strong semicomplete digraph of minimum out-degree at least 3 has a 2-out-colouring. Then, we consider the generalization of 2-out-colourings to vertex partitions (V1 , V2) of a digraph D so that each of the three digraphs induced by respectively, the vertices of V1 , the vertices of V2 and all arcs between V1 and V2 have minimum out-degree k for a prescribed integer k ≥ 1. Using probabilistic arguments, we prove that there exists an absolute positive constant c so that every tournament of minimum out-degree at least 2k + c sqrt(k) has such a partition. This is tight up to the value of c.

Joint work with N. Alon and J. Bang-Jensen.

 

Louis Esperet : Coloration distribuée avec un nombre optimal de couleurs
La coloration est un problème fondamental en algorithmique distribuée. La plupart des travaux concernent la (Delta+1)-coloration des graphes de degré maximum Delta. J'expliquerai comment gagner un peu sur le nombre de couleurs avec un algorithme qui reste très rapide.

Travail en commun avec Etienne Bamas


Nicolas Bousquet : Frozen Delta+1 colorings of Delta-regular graphs.

Let $G$ be a graph of maximum degree $\Delta$ and $k$ be an integer.
The recolouring framework consists in finding step-by-step transformations between two proper colourings such that all intermediate states are also proper. More formally, two $k$-colourings are \emph{adjacent} if they differ on exactly one vertex. The \emph{$k$-recolouring graph of $G$}, denoted by $\mathcal{C}_k(G)$ and defined for any $k\geq \chi(G)$, is the graph whose vertices are $k$-colourings of $G$, with the adjacency condition defined above. Feghali, Johnson and Paulusma [MFCS'14] showed that the $(\Delta+1)$-recolouring graph is composed by a unique connected component of size at least $2$ and (possibly many) isolated vertices.

In this paper, we study the proportion of isolated vertices (also called \emph{frozen} colourings) in the $(\Delta+1)$-recolouring graph. First we show that frozen colourings may exist even if the graph is an arbitrarily large triangle-free graph.
Our main contributions consists in showing that the proportion of isolated vertices in the $(\Delta+1)$-recolouring graph is exponentially smaller than the total number of vertices. The bound is tight up to a logarithmic factor in the exponent. This motivates the study of the Glauber dynamics on $k=\Delta+1$ colours in the unique largest component of $C_k(G)$. Finally, we show that for typical regular graphs the $(\Delta+1)$-recolouring graph is connected.


Frédéric Havet : Arbre dans les tournois
Un arbre (orienté) est n-inévitable s'il est contenu dans tous les tournois d'ordre n. Sumner a conjecturé en 1972 que tout arbre à n sommets est (2n-2)-inévitable. En 2000, Havet et Thomassé ont émis une conjecture plus forte: tout arbre à n sommets et k feuilles est (n+k-1)-inévitable. En direction de ces conjectures, nous montrons les résultats suivants:
1) toute arborescence (arbre dont tout les arcs sont orientés vers la racine) à n sommets et k feuilles est (n+k-1)-inévitable.
2) tout arbre à n sommets et k feuilles est \frac{3}{2}(n+k-1)-inévitable et (n + 164k^2)-inévitable.
3) tout arbre à n sommets est \frac{21}{8}n-inévitable.

Ce travail a été fait conjointement avec F. Dross.


Gwenaël Joret : Large independent sets in triangle-free subcubic graphs
Heckman and Thomas showed that every n-vertex planar triangle-free graph with maximum degree 3 has an independent set of size at least 3n/8, confirming a conjecture of Albertson, Bollobas and Tucker. In this talk I will present a strengthening of this result: There exists a set S of six nonplanar graphs (each of order at most 22), such that every n-vertex triangle-free graph with maximum degree 3 and having no member of S as a subgraph has an independent set of size at least
3n/8. This proves a conjecture of Fraughnaugh and Locke from 1995. A corollary of this result is that every 2-connected n-vertex triangle-free graph with maximum degree 3 has an independent set of size at least 3n/8, except for the six graphs in S.
Joint work with Wouter Cames van Batenburg and Jan Goedgebeur.


Lucas Pastor : Anciens et nouveaux résultats de coloration.

Dans un premier temps nous allons traiter d'une généralisation du problème de coloration.
Vizing (entre autres) a conjecturé dans les années 90 que pour tout line-graph, le
nombre chromatique par liste est égal au nombre chromatique. Nous nous intéresserons
à un résultat de coloration par liste dans les graphes parfaits sans griffe.
Travail en commun avec Sylvain Gravier et Frédéric Maffray.

Enfin, nous traiterons du problème de coloration (classique) dans des classes
de graphes excluant deux sous-graphe induits interdits. Ces résultats
portent sur une analyse purement structurelle permettant d'aboutir
à un algorithme polynomial de coloration pour plusieurs classes de graphes.
Travail en commun avec T. Karthick et Frédéric Maffray.


Aurélie Lagoutte : Programmation dynamique et formulations étendues

 

 

Participants :

Aboulker Pierre
Amini Omid
Aubrun Nathalie
Bessy Stéphane
Bondy Adrian
Bonnet Édouard
Bousquet Nicolas
Charbit Pierre
Esperet Louis
Harutyunyan Ararat
Havet Frédéric
Joret Gwenaël
Kim Eunjung
Lagoutte Aurélie
Lass Bodo
Lazarus Francis
Le Tien Nam
Lévêque Benjamin
Lochet William
Mary Arnaud
Newman Alantha
Parreau Aline
Pastor Lucas
Pouzet Maurice
Preissmann Myriam

Rao Michaël
Robin Cléophée
Schabanel Nicolas
Seif Johanna
Sintiari Dewi
Skomra Mateusz
Stehlik Matej
Talon Alexandre
Thomassé Stéphan
Trotignon Nicolas
Watrigant Rémi

https://www.ens-lyon.fr/LIP/MC2/journees-combinatoire-graphes-algo/ | Saved Wednesday, April 3rd, 2019 - 2:49 PM