Partitioning A Bipartite Graph into Vertex-Disjoint Paths

Abstract

Deciding whether a graph can be partitioned into \(k\) vertex-disjoint paths is a well-known NP-complete problem. In this paper, we give new sufficient conditions for a bipartite graph to be partitionable into \(k\) vertex-disjoint paths. We prove the following results for a simple bipartite graph \(G = (V_1, V_2, E)\) of order \(n\):(i) For any positive integer \(k\), if \(\|V_1| – |V_2\| \leq k\) and \(d_G(x) + d_G(y) \geq \frac{n-k+1}{2}\) for every pair \(x \in V_1\) and \(y \in V_2\) of nonadjacent vertices of \(G\), then \(G\) can be partitioned into \(k\) vertex-disjoint paths, unless \(k = 1\), \(|V_1| = |V_2| = \frac{n}{2}\) and \(G = K_{s,s} \cup K_{\frac{n}{2} – s, \frac{n}{2} – s} \cup K_{2, 2}\), where \(1 \leq k \leq \frac{n}{2} – 1\);(ii) For any two positive integers \(p_1\) and \(p_2\) satisfying \(n = p_1 + p_2\), if \(G\) does not belong to some easily recognizable classes of exceptional graphs, \(\|V_1| – |V_2\| \leq 2\) and \(d_G(x) + d_G(y) = \frac{n-1}{2}\) for every pair \(x \in V_1\) and \(y \in V_2\) of nonadjacent vertices of \(G\), then \(G\) can be partitioned into two vertex-disjoint paths \(P_{1}\) and \(P_{2}\) of order \(p_1\) and \(p_2\), respectively.These results also lead to new sufficient conditions for the existence of a Hamilton path in a bipartite graph.