Solution of fink & straight conjecture on path-perfect complete bipartite graphs
✍ Scribed by Weiting Cao; Peter Hamburger
- Publisher
- John Wiley and Sons
- Year
- 2007
- Tongue
- English
- Weight
- 213 KB
- Volume
- 55
- Category
- Article
- ISSN
- 0364-9024
No coin nor oath required. For personal study only.
✦ Synopsis
Abstract
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,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;
.
Our proof gives a linear time algorithm to find an edge disjoint partition of a complete bipartite graph into paths of lengths 1,2,3,…,n. © 2007 Wiley Periodicals, Inc. J Graph Theory 55:91–111, 2007