Seminars are given every Friday from 2:00 to 3:00 (usually in room 178, but not for the time being). 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.

See the agenda of the seminars:; to add it to yours , or flash the following QRCode:

Next talks:

The online talks are available here :

Vendredi 29 septembre ŕ 14h - Borut Lužar
Combining proper and square colorings
Proper colorings of graphs with additional distance constraints are an attractive topic in both settings: the vertex and the edge coloring. In particular, when we require that two vertices are colored differently if they are at distance at most 2, we are essentially coloring the square of a graph. Similarly, in a proper coloring of edges where two edges are colored differently as soon as they are adjacent or two of their endvertices are at distance 1, we are coloring the square of the line graph of a graph. We usually refer to the former as the square coloring and to the latter as the strong edge coloring.

Motivated by the notion of S-packing coloring, we will consider colorings with two types of colors: proper colors, which will be allowed to appear on two non-adjacent objects (regarding the setting---vertex or edge coloring), and strong colors, with which we will be able to color objects at distance at least 3 (in the edge coloring setting, the distance between two edges is taken as the distance between the corresponding vertices in the line graph). This combination of color types positions us in between the proper and the square colorings, which in most of the cases makes determination of the corresponding chromatic indices harder, but it also reveals several nice properties.

In the talk, we will focus mainly to coloring subcubic graphs and review recent results and the most interesting open problems on the topic in the vertex and the edge coloring settings.



GT Graphs and Optimization


 Previous Years

edit SideBar

Blix theme adapted by David Gilbert, powered by PmWiki