**Details:**| Published: 13 June 2014 | Created: 13 June 2014

Our weekly CRI Graphs and Combinatorics Research Seminar will meet next week in its usual time and place --

**Monday June 16 at 12:15 - Room 665, 6th floor.**

Speaker: **David Herskovics** (Eotvos Lorand Univ., Hungary) <This email address is being protected from spambots. You need JavaScript enabled to view it.>

Title: **Berge' path partition conjecture for $k geq \lambda-3$**

**Abstract:** Let D be a digraph. A path partition of D is called k-optimal if the sum of k-norms of its paths is minimal. The k-norm of a path P is $\min(|V (P)|, k)$ - specially, a 1-optimal path partition is one with a minimum number of paths Berge’s path partition conjecture claims that for every k-optimal path partition $\mathcal{P}$ there is a partial colouring of D with k colours that each path P meets $\min(|V(P)|,k)$ colours. For general digraphs the conjecture has previously been proven for $k = 1, 2, \lambda − 1, \lambda$, where $\lambda$ is the length of a longest path in the digraph.

The difficulty (and beauty) of the conjecture is that determining the min k-norm of all possible path partitions in a digraph and determining the max size of a partial k-colouring are both NP-complete problems, so we are trying to compare 2 NP-complete quantites here.

One way to approach such problem is to find some similar but easier-to-handle structures and somehow make use of them. In this talk we will see the "easier-to-handle version" of the path partition and partial k-colouring and how can they be used to prove the Berge conjecture for $k\geq \lambda-3$.

**Host:** Irith Ben-Arroyo Hartman