Seminars are given every Friday from 2:00 to 3:00 in room 178. You are welcome 10 minutes earlier for tea, coffee and cake.

In order to receive the announcements, just send an email to with subject "subscribe labri.go-gt Cookie Monster", where Cookie is your first name and Monster your last name.

Next talks:

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.



GT Graphs and Optimization


 Previous Years

edit SideBar