Some 2-Coloured 4-Cycle Decompositions

Mary Waterhouse1
1Department of Mathematics The University of Queensland Qld 4072 Australia

Abstract

There are six distinct ways in which the vertices of a 4-cycle may be coloured with two colours, called \text{colouring types}. Let \( C \) be the set of these colouring types and let \( S \) be a non-empty subset of \( C \). Suppose we colour the vertices of \( K_v \) with two colours. If \( D \) is a 4-cycle decomposition of \( K_v \) such that the colouring type of each 4-cycle is in \( S \), then \( D \) is said to have a \emph{colouring of type} \( S \). Furthermore, the colouring is said to be \emph{proper} if every colouring type in \( S \) is represented in \( D \). For all possible \( S \) of size one, two or three, excluding three cases already settled, we completely settle the existence question for 4-cycle decompositions of \( K_v \) with a colouring of type \( S \).