The terminal-pairability problem in complete bipartite graphs

Abstract In this paper, we study the terminal-pairability problem in the case that the base graph is a complete bipartite graph, and the demand graph is a bipartite graph on the same vertex set and using copies of edges of the base graph as demand edges. In 1998, Gyarfas and Schelp raised a question that if the maximum degree of the demand graph Δ ( D ) ≤ ⌈ n 3 ⌋ holds, then whether D is terminal-pairable in K n , n ? We partially answer the question.