Block colourings of 6-cycle systems

• Autorzy: Bonacini P. , Gionfriddo M. , Marino L.

Identyfikatory

DOI

10.7494/OpMath.2017.37.5.647

• Języki publikacji: EN

Abstrakty

EN

Let Σ = (X, Β) be a 6-cycle system of order v, so v ≡ 1, 9 mod 12. A c-colouring of type s is a map φ: Β) → 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 [formula], with q,r ≥ 0. φ is equitable if for every vertex x the set of the [formula] 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.

Słowa kluczowe

EN

6-cycles; block-colourings; G-decompositions

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2017
• Tom: Vol. 37, no. 5
• Strony: 647--664
• Opis fizyczny: Bibliogr. 19 poz.

Twórcy

autor

Bonacini P.

• Universita degli Studi di Catania Viale A. Doria 6, 95125 Catania, Italy

autor

Gionfriddo M.

• Universita degli Studi di Catania Viale A. Doria 6, 95125 Catania, Italy

autor

Marino L.

• Universita degli Studi di Catania Viale A. Doria 6, 95125 Catania, Italy

Bibliografia

• [1] B. Alspach, H. Gavlas, Cycle decompositions of Kn and Kn — 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 A-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 K12, J. Combin. Des. 2 (1994) 4, 273-285.
• [9] L. Gionfriddo, M. Gionfriddo, G. Ragusa, Equitable specialized block-colourings for 4-cycle systems - /, Discrete Math. 310 (2010), 3126-3131.
• [10] M. Gionfriddo, G. Quattrocchi, Colouring Jrcycle systems with equitable coloured blocks, Discrete Math. 284 (2004), 137-148.
• [11] M. Gionfriddo, G. Ragusa, Equitable specialized block-colourings for Ą-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 Kn 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 Km>n (K%,^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.

Uwagi

PL

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).