Uniquely 2-colourable 4-cycle decompositions

Andrea C. Burgess, David A. Pike, Shahriyar Pourakbar Saffar · 2026

Read Uniquely 2-colourable 4-cycle decompositions by Andrea C. Burgess, David A. Pike, Shahriyar Pourakbar Saffar (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-14804.txt.

Introduction

Burgess, Pike and Pourakbar-Saffar construct uniquely 2-colourable 4-cycle systems. A cycle system decomposes the edges of a complete graph into cycles of fixed length. It is k-colourable when vertices can be coloured with k colours so no cycle is monochromatic, and uniquely k-colourable when that colouring is unique up to permuting colour classes. The authors build uniquely 2-colourable 4-cycle systems with order n for every admissible n from forty-nine, plus decompositions of the complete graph minus a 1-factor for all admissible n from fifty.

Catalog record

CREATORAndrea C. Burgess, David A. Pike, Shahriyar Pourakbar Saffar
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE65361
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.14804

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Uniquely 2-colourable 4-cycle decompositions Andrea C. Burgess, David A. Pike, Shahriyar Pourakbar Saffar Abstract A cycle system of order n n is a decomposition of the edges of the complete graph K n K_{n} into cycles of a fixed length. A cycle system is said to be k k -colourable if we can assign k k colours to its vertices so that no cycle is monochromatic. A k k -colourable cycle system is uniquely k k -colourable if its colouring is unique up to the permutation of colour classes. In this paper, we construct uniquely 2 2 -colourable 4 4 -cycle systems of order n n for all admissible n ≥ 49 n\geq 49 , and also uniquely 2 2 -colourable 4 4 -cycle decompositions of K n − I K_{n}-I , for all admissible n ≥ 50 n\geq 50 . These constructions contribute to the broader study of uniquely colourable cycle systems and open new directions for future research. Keywords : cycle systems, graph colouring, unique colouring, combinatorial design MSC : 05C51, 05C15, 05B30 1 Introduction We begin with a few well-known definitions. For m>2 , an m -cycle decomposition of a graph G is a family of cycles of length m such that every edge of G appears in exactly one of the cycles. The necessary and sufficient conditions for the existence of an m -cycle decomposition of the complete graph K_{n} , also called an m -cycle system of order n , are that either n=1 , or n\geq m , n is odd, and m divides \frac{n(n-1)}{2} [ 1 , 2 , 15 , 16 ] . More specifically, a 4 -cycle system of order n exists if and only if n\equiv 1\ (\mathrm{mod}\ 8) . When I is a 1-factor on n vertices, it is also known that an m -cycle decomposition of the cocktail party graph K_{n}-I (i.e., the graph obtained by removing the edges of I from K_{n} ) exists if and only if either n=2 , or n\geq m , n is even, and m divides \frac{n(n-2)}{2} [ 1 , 15 , 16 ] . Consequently, a 4 -cycle decomposition of the graph K_{n}-I exists if and only if n\geq 2 is even. We use the adjective “ admissible ” for any order n that satisfies the relevant conditions for the graph in question. For a positive integer k , a weak k -colouring of an m -cycle decomposition, namely {\cal D} , of the graph G is a mapping \varphi:V(G)\rightarrow\{c_{1},\ldots,c_{k}\} that assigns one of the colours c_{1},c_{2},\ldots,c_{k} to each vertex of G in such a way that no m -cycle in the decomposition is monochromatic, i.e., for all C\in{\cal D} , \lvert\varphi(V(C))\rvert>1 . The sets \varphi^{-1}(c_{1}),\varphi^{-1}(c_{2}),\ldots,\varphi^{-1}(c_{k}) are known as the colour classes of the colouring \varphi , and \varphi partitions the vertex set of G into its nonempty colour classes. We call \varphi a balanced colouring when, for all integers i and j , \big\lvert\lvert\varphi^{-1}(c_{i})\rvert-\lvert\varphi^{-1}(c_{j})\rvert\big\rvert\leq 1 . If a weak k -colouring of {\cal D} exists, we call that decomposition weakly k -colourable , and if k is the smallest number for which {\cal D} is weakly k -colourable, we say {\cal D} is weakly k -chromatic and the weak chromatic number of {\cal D} , denoted by \chi({\cal D}) , is k . Throughout this paper we only consider weak colourings; therefore, for simplicity, the adjective “weak” and the adverb “weakly” will be omitted hereafter. The history of colouring cycle systems starts with Steiner triple systems, which also happen to be 3 -cycle systems. In 1982, de Brandes, Phelps, and Rödl proved that for every integer k\geq 3 , one can construct a k -chromatic Steiner triple system of any sufficiently large admissible order n [ 7 ] . Afterwards, in 1999, Milici and Tuza showed the existence of a 2-chromatic m -cycle system for all m>3 and for infinitely many admissible orders [ 13 ] . In the following decade, Burgess and Pike proved the existence of an m -cycle system with arbitrary chromatic number when m is even [ 3 , 4 ] . Furthermore, in 2010 Horsley and Pike extended these results by establishing that a k -chromatic m -cycle system exists for all (k,m)\neq(2,3) and for every large admissible order [ 11 ] . One may notice that the count of different ways to colour a cycle decomposition does not increase when we reduce the number of colours. Let {\cal D} be an m -cycle decomposition of a graph G on n>1 vertices, and \varphi:V(G)\rightarrow\{c_{1},\ldots,c_{k}\} be a k -colouring of {\cal D} with the colour classes C_{1},\dots,C_{k} . The decomposition {\cal D} is said to be uniquely k -colourable if any other k ‑colouring of {\cal D} , namely \psi , yields the same family of colour classes, i.e., there exists a permutation map \sigma_{\psi}:\{c_{1},\ldots,c_{k}\}\rightarrow\{c_{1},\ldots,c_{k}\} such that \varphi=\sigma_{\psi}\circ\psi . Equivalently, no two distinct k ‑colourings of the k ‑colourable m -cycle decomposition {\cal D} can produce different partitions of V(G) via their colour classes. It is worth mentioning that since \lvert V(G)\rvert>1 and m>2 , if {\cal D} is a uniquely k -colourable m -cycle decomposition of G , then this decomposition is also k -chromatic. If k\geq n , it is easy to see that {\cal D} is neither uniquely k -colourable, nor k -chromatic. If k<n , observe that any k -colouring of \cal{D} that is not surjective cannot be unique (because we can re-colour any vertex of a colour class of size at least 2 with any unused colour, thereby obtaining a different k -colouring) and so any unique colouring of \cal{D} must use all k colours and therefore is a surjective colouring. It follows that if \cal{D} is uniquely k -colourable, then \cal{D} must be k -chromatic (because any (k-1) -colouring would correspond to a k -colouring that is not surjective, indicating that there is a different k -colouring other than the supposedly unique one). Any nontrivial Steiner triple system has chromatic number at least 3 [ 14 ] and thus there are no uniquely 2-colourable Steiner triple systems of order n>3 . In 2003, Forbes built upon a few known uniquely 3 ‑colourable Steiner triple systems mentioned in [ 6 , 7 , 8 ] and showed that for every admissible order n\geq 25 , there exists a uniquely 3 ‑colourable Steiner triple system with a balanced colouring and also one with no balanced colouring [ 9 ] . Every Steiner triple system of order n , 3<n\leq 19 , is known to be 3-chromatic [ 5 , 7 ] . As mentioned in [ 8 ] , there are no uniquely 3 ‑colourable Steiner triple systems with an order smaller than 19. For those of order 19, which were enumerated in 2004 by Kaski and Östergård [ 12 ] , we have computationally verified that none of them are uniquely 3 ‑colourable. As there are 14,796,207,517,873,771 non-isomorphic Steiner triple systems of order 21 [ 10 ] , it is currently infeasible to check their 3-colourings. That is where the prior knowledge of uniquely colourable cycle decompositions ends. In this paper, we push it further by affirmatively answering the questions “Do

Read the complete text