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

Gaetano Quattrocchi

The electronic journal of combinatorics, Tome 8 (2001) no. 1

Résumé

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$.

Détail

DOI : 10.37236/1568

Classification : 05B05
Mots-clés : graph design, \(m\)-colouring, path, cycle