Some Open Problems on Directed Graphs

Abstract:

We shall discuss a number of related open problems and conjectures on directed graphs, all of which have very simple statements but which seem remarkably hard to solve. They include a $40$-year-old conjecture of Gallai on circuit coverings, a 25-year-old conjecture of Hansen on semi-kernels, a 20-year-old conjecture of Caccetta and Haggkvist on triangles, and a more recent conjecture of Seymour and Winkler on second neighbourhoods. Directed graphs are particularly intriguing objects to deal with. The right approach often leads to a very short proof, as we shall illustrate. Finding this elusive key is another matter.