Highly parity linked graphs (Q987554)

The subject of the paper originates on the Erdős-Pósa property of graphs [\textit{P. Erdős} and \textit{L. Pósa}, Publ. Math. 9, 3--12 (1962; Zbl 0133.16701)]. A family \(\mathcal F\) of graphs has this this property if for every \(k \in N\) there is an integer \(f(k,\mathcal{F})\) such that any graph \(G\) is either contains \(k\) vertex disjoint graphs from \(\mathcal F\), or there is an \(X \subset V(G)\) such that \(G - X\) contains none. They showed the family of cycles has the Erdős-Pósa property. \textit{C. Thomassen} [Combinatorica 21, No. 2, 321--333 (2001; Zbl 0989.05062)] showed that while in general the family of odd cycles does not have the Erdős-Pósa property, there is a function \(f\) such that if \(G\) is \(f(k)\)-connected then either \(G\) contains \(k\) disjoint odd cycles or \(G\) becomes bipartite after deleting an appropriate set \(X \subset V(G)\) of size \(2k-2\). The disjoint odd cycles are in close relation with the following notion. A graph \(G\) is \(k\)-linked if it has at least \(2k\) vertices, and for any \(2k\) vertices \(x_1, \dots, x_k\), \(y_1, \dots, y_k\) there are \(k\) pairwise disjoint paths \(P_1, \dots, P_k\) such that \(P_i\) connects \(x_i\) and \(y_i\) for all \(i=1, \dots, k\). \textit{H. A. Jung} [Math. Ann. 187, 95--103 (1970; Zbl 0184.27601)] and \textit{D. G. Larman} and \textit{P. Mani} [Proc. Lond. Math. Soc., III. Ser. 20, 144--160 (1970; Zbl 0201.56801)] proved the existence of an \(f(k)\) such that every \(f(k)\)-connected graph is \(k\)-linked. (Note that the paper of Larman and Mani is incorrectly dated in this paper.) For that case \textit{R. Thomas} and \textit{P. Wollan} [Eur. J. Comb. 26, No. 3-4, 309-324 (2005; Zbl 1056.05091)] had the best result as every \(10k\)-connected graph is \(k\)-linked. \(G\) is parity-\(k\)-linked if the parity of each \(P_i\) can be described. In the above mentioned paper Thomassen generalized his results as there exist functions \(f(k)\) and \(g(k)\) such that if a graph \(G\) is \(f(k)\)-connected, then it is either parity-\(k\)-linked or for some \(X \subset V(G)\) the subgraph \(G-X\) is bipartite. In fact, the exact value is \(g(k)=4k-3\). The main theorem of this paper is the improvement of \(f(k)\), while Thomassen gave a double exponential upper bound, the authors show that \(f(k)=50k\) is enough. Their proof also improves the former results on odd cycles: A \(24k\)-connected graph \(G\) has either \(k\) disjoint cycles or a set \(X \subset V(G)\) such that \(| X| \leq 2k-2\) and \(G-X\) is bipartite.