Opuscula Math. 37, no. 5 (2017), 647-664
http://dx.doi.org/10.7494/OpMath.2017.37.5.647

Opuscula Mathematica

# Block colourings of 6-cycle systems

Paola Bonacini
Mario Gionfriddo
Lucia Marino

Abstract. Let $$\Sigma=(X,\mathcal{B})$$ be a $$6$$-cycle system of order $$v$$, so $$v\equiv 1,9\mod 12$$. A $$c$$-colouring of type $$s$$ is a map $$\phi\colon\mathcal {B}\rightarrow \mathcal{C}$$, with $$C$$ set of colours, such that exactly $$c$$ colours are used and for every vertex $$x$$ all the blocks containing $$x$$ are coloured exactly with $$s$$ colours. Let $$\frac{v-1}{2}=qs+r$$, with $$q, r\geq 0$$. $$\phi$$ is equitable if for every vertex $$x$$ the set of the $$\frac{v-1}{2}$$ blocks containing $$x$$ is partitioned in $$r$$ colour classes of cardinality $$q+1$$ and $$s-r$$ colour classes of cardinality $$q$$. In this paper we study bicolourings and tricolourings, for which, respectively, $$s=2$$ and $$s=3$$, distinguishing the cases $$v=12k+1$$ and $$v=12k+9$$. In particular, we settle completely the case of $$s=2$$, while for $$s=3$$ we determine upper and lower bounds for $$c$$.

Keywords: 6-cycles, block-colourings, G-decompositions.

Mathematics Subject Classification: 05C15, 05B05.

Full text (pdf)

1. B. Alspach, H. Gavlas, Cycle decompositions of $$K^n$$ and $$K^n-I$$, J. Combin. Theory Ser. B 81 (2001), 77-99.
2. G. Bacso, Zs. Tuza, V. Voloshin, Unique colourings of bi-hypergraphs, Australas. J. Combin. 27 (2003), 33-45.
3. P. Bonacini, L. Marino, Equitable tricolourings for 4-cycle systems, Applied Mathematical Sciences 9 (2015) 58, 2881-2887.
4. P. Bonacini, L. Marino, Equitable block colourings, Ars Comb. 120 (2015), 255-258.
5. Cs. Bujtas, Zs. Tuza, V. Voloshin, Hypergraph Colouring, [in:] L.W. Beineke, R.J. Wilson (eds), Topics in Chromatic Graph Theory, Cambridge University Press, 2015, 230-254.
6. P. Cameron, Parallelisms in complete designs, Cambridge University Press, Cambridge, 1976.
7. C.J. Colbourn, A. Rosa, Specialized block-colourings of Steiner triple systems and the upper chromatic index, Graphs Combin. 19 (2003), 335-345.
8. J.H. Dinitz, D.K. Garnick, B.D. McKay, There are 526,915,620 nonisomorphic one-factorizations of $$K_{12}$$, J. Combin. Des. 2 (1994) 4, 273-285.
9. L. Gionfriddo, M. Gionfriddo, G. Ragusa, Equitable specialized block-colourings for 4-cycle systems - I, Discrete Math. 310 (2010), 3126-3131.
10. M. Gionfriddo, G. Quattrocchi, Colouring 4-cycle systems with equitable coloured blocks, Discrete Math. 284 (2004), 137-148.
11. M. Gionfriddo, G. Ragusa, Equitable specialized block-colourings for 4-cycle systems - II, Discrete Math. 310 (2010), 1986-1994.
12. M. Gionfriddo, P. Horak, L. Milazzo, A. Rosa, Equitable specialized block-colourings for Steiner triple systems, Graphs Combin. 24 (2008), 313-326.
13. J.A. Kennedy, Maximum packings of $$K_n$$ with hexagons, Australas. J. Combin. 7 (1993), 101-110.
14. S. Milici, A. Rosa, V. Voloshin, Colouring Steiner systems with specified block colour pattern, Discrete Math. 240 (2001), 145-160.
15. A. Rosa, C. Huang, Another class of balanced graph designs: balanced circuit designs, Discrete Math. 12 (1975) 3, 269-293.
16. B.R. Smith, Decomposing complete equipartite graphs into cycles of length $$2p$$, J. Comb. Des. 16 (2008) 3, 244-252.
17. D. Sotteau, Decompositions of $$K_{m,n}$$ ($$K^{\star}_{m,n}$$) into cycles (circuits) of length $$2k$$, J. Comb. Theory B, 30 (1981), 75-81.
18. V. Voloshin, Coloring block designs as mixed hypergraphs: survey, Abstracts of papers presented to the American Mathematical Society (2005), vol. 26, no. 1, issue 139, p. 15.
19. V. Voloshin, Graph Coloring: History, results and open problems, Alabama Journal of Mathematics, Spring/Fall 2009.
• Paola Bonacini
• Università degli Studi di Catania, Viale A. Doria 6, 95125 Catania, Italy
• Mario Gionfriddo
• Università degli Studi di Catania, Viale A. Doria 6, 95125 Catania, Italy
• Lucia Marino
• Università degli Studi di Catania, Viale A. Doria 6, 95125 Catania, Italy
• Communicated by Mariusz Meszka.
• Revised: 2016-12-10.
• Accepted: 2016-12-21.
• Published online: 2017-07-05.