On the general problem of Erdos and Nesetril and its offsprings.

Abstract: In 1988, Erdos wrote about a problem he proposed with Nesetril:

“One could perhaps try to determine the smallest integer h_t(D) for which every graph, with size h_t(D) edges and maximum degree at most D, contains two edges so that the shortest path joining these edges has length at least t. This problem seems to be interesting only if there is a nice expression for h_t(D).”

This problem can be considered as the edge version of the famous (and hard) degree-diameter problem.

It was the inspiration for a series of research papers on variants of this problem, where one is mainly dealing with the case t=2. We will discuss part of the history that resulted in the strong edge colouring conjecture, which is still widely open.

In the second part of the talk, we will look again to the initial inspirational question of all of this and say more about the cases where t is at least 3.

Posted on Jun 29, 2021 in ACGO, Seminars