When: Sunday, May 7, 10am
Where: Schreiber 309
Speaker: Peter L. Erdos (Renyi Institute, Budapest)
Title: Terminal-Pairability in Complete Bipartite Graphs
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.
