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.
- B. Alspach, H. Gavlas, Cycle decompositions of \(K^n\) and \(K^n-I\), J. Combin. Theory Ser. B 81 (2001), 77-99.
- G. Bacso, Zs. Tuza, V. Voloshin, Unique colourings of bi-hypergraphs, Australas. J. Combin. 27 (2003), 33-45.
- P. Bonacini, L. Marino, Equitable tricolourings for 4-cycle systems, Applied Mathematical Sciences 9 (2015) 58, 2881-2887.
- P. Bonacini, L. Marino, Equitable block colourings, Ars Comb. 120 (2015), 255-258.
- 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.
- P. Cameron, Parallelisms in complete designs, Cambridge University Press, Cambridge, 1976.
- C.J. Colbourn, A. Rosa, Specialized block-colourings of Steiner triple systems and the upper chromatic index, Graphs Combin. 19 (2003), 335-345.
- 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.
- L. Gionfriddo, M. Gionfriddo, G. Ragusa, Equitable specialized block-colourings for 4-cycle systems - I, Discrete Math. 310 (2010), 3126-3131.
- M. Gionfriddo, G. Quattrocchi, Colouring 4-cycle systems with equitable coloured blocks, Discrete Math. 284 (2004), 137-148.
- M. Gionfriddo, G. Ragusa, Equitable specialized block-colourings for 4-cycle systems - II, Discrete Math. 310 (2010), 1986-1994.
- M. Gionfriddo, P. Horak, L. Milazzo, A. Rosa, Equitable specialized block-colourings for Steiner triple systems, Graphs Combin. 24 (2008), 313-326.
- J.A. Kennedy, Maximum packings of \(K_n\) with hexagons, Australas. J. Combin. 7 (1993), 101-110.
- S. Milici, A. Rosa, V. Voloshin, Colouring Steiner systems with specified block colour pattern, Discrete Math. 240 (2001), 145-160.
- A. Rosa, C. Huang, Another class of balanced graph designs: balanced circuit designs, Discrete Math. 12 (1975) 3, 269-293.
- B.R. Smith, Decomposing complete equipartite graphs into cycles of length \(2p\), J. Comb. Des. 16 (2008) 3, 244-252.
- 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.
- 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.
- 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.
- Received: 2016-09-19.
- Revised: 2016-12-10.
- Accepted: 2016-12-21.
- Published online: 2017-07-05.
