Les GT se tiennent chaque vendredi de 14h à 15h en salle 178. Vous êtes invités à venir 10 minutes avant pour partager thé, café et gâteaux.

Pour vous inscrire à la liste de diffusion, il suffit d'envoyer un mail à sympa@diff.u-bordeaux.fr avec pour sujet "subscribe labri.go-gt Cookie Monster", où Cookie est remplacé par votre prénom et Monster par votre nom.

Prochains exposés :

Vendredi 22 février 2019 - Trees in tournaments - François Dross (I3S, Inria Sophia Antipolis).

A tournament is an orientation of a complete graph. A digraph D is said to be k-unavoidable if it is contained in every tournament of order k. As the transitive tournament of order n is (2^(n-1))-unavoidable, every graph of order n is (2^(n-1))-unavoidable. However, for some particular digraphs one can obtain a better bound.

In this presentation we will focus on orientations of trees. Sumner conjectured that every tree of order n > 1 is (2n-2)-unavoidable, and Havet and Thomassé made the strengthened conjecture that every tree of order n > 1 with k leaves is (n+k-1)-unavoidable. We will see some techniques to approach these conjectures.

Vendredi 22 mars 2019 - Local analogues of classic results in Hamiltonian graph theory - Jonas Börje Granholm (Linköping University, Suède).

Many classic criteria for the existence of Hamiltonian cycles in graphs relate vertex degrees to the number of vertices in the entire graph. Perhaps the most famous such result is the one by Dirac, which states that a graph G is Hamiltonian if every vertex of G is adjacent to at least half of all vertices of G. The classes of graphs covered by such theorems are necessarily limited to dense graphs of small diameter.

Beginning in the 1980’s, Asratian and Khachatryan pioneered a method to overcome this limitation, by instead considering local structures of graphs. They obtained several generalizations of well-known sufficient conditions for Hamiltonicity, for instance the following generalization of Dirac’s theorem: A graph G is Hamiltonian if every vertex u of G is adjacent to at least half of all vertices at distance at most 3 from u. In this talk we will discuss this localization method, and some recent results in the area.


Emplois - Stages

Groupe

GT Graphes et Optimisation

Historique

edit SideBar