Highly parity linked graphs.

Abstract  A graph G is k-linked if G has at least 2k vertices, and for any 2k vertices x 1,x 2, …, x k ,y 1,y 2, …, y k , G contains k pairwise disjoint paths P 1, …, P k such that P i joins x i and y i for i = 1,2, …, k. We say that G is parity-k-linked if G is k-linked and, in addition, the paths P 1, …, P k can be chosen such that the parities of their length are prescribed. Thomassen [22] was the first to prove the existence of a function f(k) such that every f(k)-connected graph is parity-k-linked if the deletion of any 4k-3 vertices leaves a nonbipartite graph. In this paper, we will show that the above statement is still valid for 50k-connected graphs. This is the first result that connectivity which is a linear function of k guarantees the Erdős-Pósa type result for parity-k-linked graphs. [ABSTRACT FROM AUTHOR]