Colouring \(4\)-cycle systems with specified block colour patterns: The case of embedding \(P_3\)-designs (Q5934271): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 01:41, 30 January 2024
scientific article; zbMATH DE number 1606451
Language | Label | Description | Also known as |
---|---|---|---|
English | Colouring \(4\)-cycle systems with specified block colour patterns: The case of embedding \(P_3\)-designs |
scientific article; zbMATH DE number 1606451 |
Statements
Colouring \(4\)-cycle systems with specified block colour patterns: The case of embedding \(P_3\)-designs (English)
0 references
19 June 2001
0 references
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\).
0 references
graph design
0 references
\(m\)-colouring
0 references
path
0 references
cycle
0 references