Cyclic‐order graphs and Zarankiewicz's crossing‐number conjecture

Zarankiewicz's conjecture, that the crossing number of the complete‐bipartite graph K m, n is [1/2 m ] [1/2 ( m ] −1) [1/2 n ] [1/2 ( n −1)], was proved by Kleitman when min( m, n ) ≤ 6, but was unsettled in all other cases. The cyclic‐order graph CO n arises naturally in the study of this conjecture; it is a vertex‐transitive harmonic diametrical (even) graph. In this paper the properties of cyclic‐order graphs are investigated and used as the basis for computer programs that have verified Zarankiewicz's conjecture for K 7,7 and K 7,9 ; thus the smallest unsettled cases are now K 7,11 and K 9,9 . © 1993 John Wiley & Sons, Inc.