On a conjecture of Linial and Berge
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.