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 \({colouring\; of\; type}\) \( S \). Furthermore, the colouring is said to be \({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 \).