Colouring \(4\)-cycle systems with specified block colour patterns: The case of embedding \(P_3\)-designs (Q5934271)

Summary: A colouring of a \(4\)-cycle system \((V,{\mathcal 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,{\mathcal B})\). For every \(B\in{\mathcal B}\), let \(\phi(B)=\{\phi(x)\mid 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,{\mathcal B})\) is said to be of type \(S\) if the type of every \(4\)-cycle of \(\mathcal 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 \(\mathcal B\) having colour type \(\alpha\). We say that a \(P(v,3,1)\), \((W,{\mathcal P})\), is embedded in a \(4\)-cycle system of order \(n\), \((V,{\mathcal B})\), if every path \(p=[a_1,a_2,a_3] \in {\mathcal P}\) occurs in a \(4\)-cycle \((a_1,a_2,a_3,x) \in {\mathcal B}\) such that \(x \not\in 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 such a 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\).