Colouring $4$-cycle Systems with Specified Block Colour Patterns: the Case of Embedding $P_3$-designs

Abstract

A colouring of a $4$-cycle system $(V,{\cal B})$ is a surjective mapping $\phi : V \rightarrow \Gamma$. The elements of $\Gamma$ are colours. If $|\Gamma|=m$, we have an $m$-colouring of $(V,{\cal B})$. For every $B\in{\cal B}$, let $\phi(B)=\{\phi(x) | x\in B\}$. There are seven distinct colouring patterns in which a $4$-cycle can be coloured: type $a$ (${\times}{\times}{\times}{\times}$, monochromatic), type $b$ (${\times}{\times}{\times}{\square}$, two-coloured of pattern $3+1$), type $c$ (${\times}{\times}{\square}{\square}$, two-coloured of pattern $2+2$), type $d$ (${\times}{\square}{\times}{\square}$, mixed two-colored), type $e$ (${\times}{\times}{\square}{\triangle}$, three-coloured of pattern $2+1+1$), type $f$ (${\times}{\square}{\times}{\triangle}$, mixed three-coloured), type $g$ (${\times}{\square}{\triangle}{\diamondsuit}$, four-coloured or polychromatic).

Let $S$ be a subset of $\{a,b,c,d,e,f,g\}$. An $m$-colouring $\phi$ of $(V,{\cal B})$ is said of type $S$ if the type of every $4$-cycle of $\cal B$ is in $S$. A type $S$ colouring is said to be proper if for every type $\alpha \in S$ there is at least one $4$-cycle of $\cal B$ having colour type $\alpha$.

We say that a $P(v,3,1)$, $(W,{\cal P})$, is embedded in a $4$-cycle system of order $n$, $(V,{\cal B})$, if every path $p=[a_1,a_2,a_3] \in {\cal P}$ occurs in a $4$-cycle $(a_1,a_2,a_3,x) \in {\cal B}$ such that $x \notin W$.

In this paper we consider the following spectrum problem: given an integer $m$ and a set $S \subseteq \{b,d,f\}$, determine the set of integers $n$ such that there exists a $4$-cycle system of order $n$ with a proper $m$-colouring of type $S$ (note that each colour class of a such coloration is the point set of a $P_3$-design embedded in the $4$-cycle system).

We give a complete answer to the above problem except when $S=\{b\}$. In this case the problem is completely solved only for $m=2$.