Equitable block-colorings of C 4 -decompositions of K v - F

In this paper we consider the existence of ( s , p )-equitable block-colorings of 4-cycle decompositions of K v - F , where F is a 1-factor of K v . In such colorings, the 4-cycles are colored with s colors in such a way that, for each vertex u , the 4-cycles containing u are colored with p colors so that the number of such 4-cycles of each color is within one of the number of such 4-cycles of each of the other p - 1 colors. Of primary interest is settling the values of ? p ' ( v ) and ? ? p ' ( v ) , namely the least and greatest values of s for which there exists such a block-coloring of some 4-cycle decomposition of K v - F . In this paper, several general results are established, both existence and non-existence theorems. These are then used to find, for all possible values of v , the values of ? p ' ( v ) when p ? { 2 , 3 , 4 } and ? ? 2 ' ( v ) , and to provide good upper bounds on ? ? 3 ' ( v ) .