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 25 octobre 2019 - "On directed versions of the 1-2-3 Conjecture and the 1-2 Conjecture" - Mariusz Wozniak (Krakow, Pologne).
Let G = (V, E) be a graph. Given an integer k, a k-coloring (labeling) of G is a function f : E → {1, 2, . . . , k}. The coloring f can be represented by substituting each edge e of G by a multiedge with multiplicity f(e). The degree of x in the respective multigraph equals the sum of labels around a vertex x. The 1-2-3 Conjecture says that for graphs without isolated edges there exists a 3-coloring f such the the corresponding multigraph is locally irregular i.e. for each edge xy of G we have σ(x) = σ(y) where σ(x) = Sum_{x in e} f(e). The 1-2 Conjecture refers to the case when we also color the vertices. During the talk we shall look at the directed versions of these problems. We will discuss the results contained in the papers listed in the references below.

[1] E. Barme, J. Bensmail, J. Przyby lo, M. Wo´zniak, On a directed variation of the 1-2-3 and 1-2 Conjectures, Discrete Appl. Math. 217 (2017) 123–131.
[2] O. Baudon, J. Bensmail, E. Sopena, An oriented version of the 1-2-3 Conjecture, Discuss. Math. Graph Theory 35(1) (2015) 141–156.
[3] M. Borowiecki, J. Grytczuk, M. Pil´sniak, Coloring chip configurations on graphs and digraphs, Inform. Process. Lett. 112 (2012) 1–4.
[4] M. Horˇn´ak, J. Przyby lo, M. Wo´zniak, A note on a directed version of the 1-2-3 Conjecture, Discrete Applied Math. 236 (2018), 472-476.

Vendredi 8 novembre 2019 - "10 years of identification problems in graphs: selected topics" - Florent Foucaud (LaBRI).

Vendredi 22 novembre 2019 - "Split-decomposition" pour des graphes orientés et non orientés; majorations de la largeur de clique" (en français) - Bruno Courcelle (LaBRI).



GT Graphs and Optimization


 Previous Years

edit SideBar