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 19 avril 2019 - Distance Constrained Graph Labeling - Soumen Nandi (Institute of enginerring & Management, Kolkata, Inde,).

In a cellular network, the channel assignment problem (CAP) is the task of assigning channels (frequency, time, code etc.) to the cells (base stations) satisfying the constraints to avoid channel interference. The degree of interference between base stations is related to the distance between them; closer the base stations stronger the interference. So in order to avoid interference, closer base stations should have higher channel difference. The aim is to allocate channels such that span (bandwidth) is minimized. The span is the difference between the least and the highest channels used. A channel assignment problem can be modeled on a graph, whose vertices represent the cells and edges represent possible communications and hence, interferences. Usually, most of these graph theoretic models of a CAP assume communication in both directions (duplex) between two transmitters/receivers and hence the CAP is modeled on a simple undirected graph.

Here, we will discuss a general technique for computing the lower bound of the span for radio k-chromatic number of a general graph G and derive a formula for it. We will also discuss some results to find optimal bounds of the span of different channel assignment problems modeled on undirected graphs.

Vendredi 26 avril 2019 - Star Edge-Coloring - Borut Lužar (Faculty of Information Studies in Novo mesto, Slovénie).

(joint work with M. Mockovčiaková, R. Soták, L. Šebestová & R. Škrekovski)

A star edge-coloring of a graph is a proper edge-coloring with forbidden bichromatic paths and cycles of length 4. The least number of colors that suffice for an edge-coloring of a graph G is called the star chromatic index, denoted χ'st(G). Motivated by the vertex analogue, the notion has been introduced in 2008 by Liu and Deng, who proved the first upper bound on the star chromatic index of any graph with maximum degree at least 7. Currently the best upper bound for general graphs has been established by Dvořák, Mohar, and Šámal in 2013 using their upper bound on the star chromatic index of complete graphs. They showed that for every ε > 0 there exists a constant C such that χ'st(G)<= C.n^(1+ε) for every positive n. They asked if the star chromatic index of complete graphs Kn is linear in terms of n. The answer to this question is still not known. Apart from the above, the same authors also considered subcubic graphs, proved that for any subcubic graph 7 colors suffice for a star edge-coloring, conjectured that the bound can be decreased to 6, and asked about the bounds for the list version of star edge-coloring. All these questions initiated an intense (and still ongoing) research on the topic. In the talk, we will give a survey of known results, present the most interesting proofs and techniques, and propose additional possible directions of research on the topic.

Vendredi 3 mai 2019 - TBA - Carol Zamfirescu (Ghent University, Belgique).



GT Graphs and Optimization


 Previous Years

edit SideBar