Cycle systems without 2-colorings

In an m-cycle system C of order n the blocks are the vertex sets of n(n−1)/(2m) cycles C_i such that each edge of the complete graph K_n belongs to precisely one cycle C_i E C. We prove the existence of m-cycle systems that admit no vertex partition into two classes in such a way that each class meets every cycle of C. The proofs apply both constructive and probabilistic methods, and also some old and new facts about Steiner Triple Systems without large independent sets. © 1996 John Wiley & Sons, Inc.