Atlantic Graph Theory Seminar

Speaker: Shahriyar Pourakbar Saffar, Memorial University of Newfoundland

Title: Existence of uniquely 2-colourable 4-cycle decompositions: A constructive proof

Abstract: A cycle system of order $n$ is a decomposition of the edges of the complete graph $K_n$ into cycles of a fixed length. A cycle system is said to be $k$-colourable if we can assign $k$ colours to its vertices so that no cycle is monochromatic. If a cycle system is $k$-colourable but not $(k-1)$-colourable, it is called $k$-chromatic. A $k$-colourable cycle system is uniquely $k$-colourable if its colouring is unique up to the permutation of colour classes.

The study of colouring cycle systems has been explored in various settings. In particular, Horsley and Pike have examined the existence of $k$-chromatic $m$-cycle systems for any integers $m>2$ and $k>1$. While Forbes has investigated $3$-cycle systems with unique $3$-colourability, the existence of uniquely $k$-colourable $m$-cycle systems in general remains an open problem.

In this talk, we mainly focus on the construction of an infinite family of uniquely $2$-colourable $4$-cycle systems and also a uniquely $2$-colourable $4$-cycle decomposition of $K_n – I$, for infinitely many integers $n \geq 2$. These constructions contribute to the broader study of uniquely colourable cycle systems and open new directions for future research.

Zoom link:

Meeting ID: 880 1326 1876