# Combinatorics Seminar

When: Sunday, May 7, 10am

Where: Schreiber 309

Speaker: Peter L. Erdos (Renyi Institute, Budapest)

Title: Terminal-Pairability in Complete Bipartite Graphs

## Abstract:

The terminal-pairability problem has been introduced by Csaba, Faudree,
Gyarfas, Lehel and Schelp in 1992. It asks the following question: given
a simple base graph G and a list of pairs of vertices of G (which may
contain multiple copies of the same pair), can we assign to each pair
a path in G whose end-vertices are the two elements of the pair, such
that the set of chosen paths are pairwise edge-disjoint? The demands
can be described compactly by a so called demand graph.

The problem emerged from a practical computer net problem.

In this talk we investigate the terminal-pairibility problem in the case
when the base graph is a complete bipartite graph, and the demand graph
is also bipartite with the same color classes. We improve the lower
bound on the maximum value of Delta(D) which still guarantees that the
demand graph D is terminal-pairable in this setting. We also prove a
sharp theorem on the maximum number of edges such a demand graph can have.

Joint work with L. Colucci, E. Gyori and T.R Mezei.

redesigned by barak soreq