On a Conjecture of Linial and Berge

COMPUTER SCIENCE/DISCRETE MATH I
Topic:On a Conjecture of Linial and Berge
Speaker:Eli Berger
Affiliation:University of Haifa
Date:Monday, September 15
Time/Room:11:15am - 12:15pm/S-101

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