Vendredi 9 octobre à 14h - Alexandre Blanché
Gallai's path decomposition conjecture for planar graphs
Connexion: et salle 178 (hybride)

In 1968, Gallai conjectured that the edges of any connected graph on n vertices can be partitioned into at most (n+1)/2 egde-disjoint paths. This conjecture is still open to this day, but was proved on some graph classes such as graphs with at most one vertex of even degree (Lovász, 1968), graphs with maximum degree at most 5 (Bonamy et al., 2016) or graphs with treewidth at most 3 (Botler et al., 2017). We proved the conjecture on the class of planar graphs, i.e. graphs that can be drawn in the plane with no edges crossing. More precisely, we proved a stronger result: any connected planar graph on n vertices can be decomposed into at most n/2 paths, except K3 and K5 minus one edge.

(Based on joint works with Marthe Bonamy and Nicolas Bonichon)

Vendredi 2 octobre à 14h - Nicolas Bousquet
Independent Set Reconfiguration via Token Sliding

An independent set of a graph G is a subset of pairwise non incident vertices of G. Finding a maximum independent set in G is a problem that received a considerable attention in the last decades. In this talk, we will look at this problem via the lens of reconfiguration. Two independent sets X,Y are said to be adjacent (in the Token Sliding (TS) model) if there exist two vertices x,y such that X-x= Y-y. A TS-sequence of independent sets is a sequence of independent sets such that any pair of consecutive independent sets in the sequence are TS-adjacent.

In 2005, Hearn and Demaine showed that it is PSPACE-complete to determine, given two k-independent sets X,Y of G if there exists a TS-sequence between X and Y. This result had important consequences and opened a new direction of research. Since then, numerous results have been obtained. We will overview some of the most relevant results in this field and mention some possible future research directions.

(Based on joint works with Valent Bartier, Marthe Bonamy, Clément Dallard, Kyle Lomer, Amer Mouawad, Moritz Mühlenthaler)

Vendredi 25 septembre à 14h - Jonathan Narboni
On Vizing's edge coloring question

In his 1965 seminal paper on edge coloring, Vizing proved that a (Delta+1)-edge coloring can be reached from any given proper edge coloring through a series of Kempe changes, where Delta is the maximum degree of the graph. He concludes the paper with the following question: can an optimal edge coloring be reached from any given proper edge coloring through a series of Kempe changes? In other words, if the graph is Delta-edge-colorable, can we always reach a Delta-edge-coloring? We discuss a key ingredient in Vizing's original paper, namely the use of fans; we show how to extend the notion and answer his question in the affirmative for all triangle-free graphs.

Vendredi 18 septembre à 14h - Rose McCarty
Colouring visibility graphs

We discuss recent chi-boundedness results on visibility graphs. The visibility graph of a finite set of points S on a Jordan curve J has vertex set S, and two points in S are adjacent if the (open) segment between them is contained in the interior of J. We prove that such a graph with clique number w has chromatic number at most 3*4^{w-1}, and that w can be computed in polynomial time. Moreover, these results hold in the pseudo-visibility setting. While we focus on colouring, the talk will also serve as an introduction to visibility graphs.

This is joint work with James Davies, Tomasz Krawczyk, and Bartosz Walczak.

Vendredi 11 septembre à 14h - Irena Penev
Coloring certain even-hole-free graphs

Abstract here

Emplois - Stages


GT Graphes et Optimisation


edit SideBar