Solution of Fink & Straight conjecture on path-perfect complete bipartite graphs

We consider various edge disjoint partitions of complete bipartite graphs, One case is where we decompose the edge set into edge disjoint paths of increasing lengths. A graph G is path-perfect if there is a positive integer n such that the edge set E(G) of the graph G can be partitioned into paths of length 1,2,3,...,n. The main result of the paper is the proof of the conjecture of Fink and Straight [4]: A complete bipartite graph K-s,K-t on t+ s vertices (t <= s) is path-perfect if and only if there is a positive integer n such that the following two conditions are satisfied; [GRAPHICS] Our proof gives a linear time algorithm to find an edge disjoint partition of a complete bipartite graph into paths of lengths 1,2,. n. (c) 2007 Wiley Periodicals,