Computer Science/Discrete Mathematics Seminar I

In 1982 Linial and Berge conjectured that there is some form of duality between partitioning the vertices of a directed graph to disjoint paths and finding a big set of vertices in it with a small chromatic number. In the talk I will discuss the evolution of this problem from posets to acyclic digraphs and to general digraphs and what is known so far about it. This is joint work with Irith Ben-Arroyo Hartman