David Herskovics

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

Speaker: David Herskovics (Eotvos Lorand Univ., Hungary) <huncros@gmail.com>

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