×

Colouring games based on autotopisms of Latin hyper-rectangles. (English) Zbl 1420.05114

Summary: Every partial colouring of a Hamming graph is uniquely related to a partial Latin hyper-rectangle. In this paper we introduce the \(\Theta\)-stabilized \((a,b)\)-colouring game for Hamming graphs, a variant of the \((a,b)\)-colouring game so that each move must respect a given autotopism \(\Theta\) of the resulting partial Latin hyperrectangle. We examine the complexity of this variant by means of its chromatic number. We focus in particular on the bi-dimensional case, for which the game is played on the Cartesian product of two complete graphs, and also on the hypercube case.

MSC:

05C57 Games on graphs (graph-theoretic aspects)
05C15 Coloring of graphs and hypergraphs
05B15 Orthogonal arrays, Latin squares, Room squares
05C76 Graph operations (line graphs, products, etc.)
91A43 Games involving graphs

Software:

pls.lib
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Andres, S. D., Spieltheoretische Kantenfärbungsprobleme auf Wäldern und verwandte Strukturen (2003), Universität zu Köln
[2] Andres, S. D., The game chromatic index of forests of maximum degree Δ 5, Discrete Appl. Math., 154, 1317-1323 (2006) · Zbl 1091.05023 · doi:10.1016/j.dam.2005.05.031
[3] Andres, S. D., Asymmetric directed graph coloring games, Discrete Math., 309, 5799-5802 (2009) · Zbl 1177.91054 · doi:10.1016/j.disc.2008.03.022
[4] Andres, S. D., Game-perfect graphs, Math. Methods Oper. Res., 69, 235-250 (2009) · Zbl 1161.91331 · doi:10.1007/s00186-008-0256-3
[5] Bartnicki, T.; Brešar, B.; Grytczuk, J.; Kovše, M.; Miechowicz, Z.; Peterin, I., Game chromatic number of Cartesian product graphs, Electron. J. Comb., 15 (2008) · Zbl 1178.05039
[6] Bartnicki, T.; Grytczuk, J.; Kierstead, H. A.; Zhu, X., The map-coloring game, Am. Math. Mon., 114, 793-803 (2007) · Zbl 1247.05074 · doi:10.1080/00029890.2007.11920471
[7] Besharati, N.; Goddyn, L.; Mahmoodian, E. S.; Mortezaeefar, M., On the chromatic number of Latin square graphs, Discrete Math., 339, 2613-2619 (2016) · Zbl 1339.05036 · doi:10.1016/j.disc.2016.04.025
[8] Bodlaender, H. L., On the complexity of some coloring games, Int. J. Found. Comput. Sci., 2, 133-147 (1991) · Zbl 0753.05061 · doi:10.1142/S0129054191000091
[9] Bose, R. C., Strongly regular graphs, partial geometries and partially balanced designs, Pacific J. Math., 13, 389-419 (1963) · Zbl 0118.33903 · doi:10.2140/pjm.1963.13.389
[10] Browning, J.; Stones, D. S.; Wanless, I. M., Bounds on the number of autotopisms and subsquares of a Latin square, Combinatorica, 33, 11-22 (2013) · Zbl 1299.05028 · doi:10.1007/s00493-013-2809-1
[11] Bryant, D.; Buchanan, M.; Wanless, I. M., The spectrum for quasigroups with cyclic automorphisms and additional symmetries, Discrete Math., 304, 821-833 (2009) · Zbl 1221.20047 · doi:10.1016/j.disc.2008.01.020
[12] Bryant, D.; Maenhaut, B.; Wanless, I., New families of atomic Latin squares and perfect 1-factorisations, J. Combin. Theory Ser. A, 113, 608-624 (2006) · Zbl 1089.05058 · doi:10.1016/j.jcta.2005.05.003
[13] Dénes, J.; Keedwell, A. D., Latin squares: New developments in the theory and applications, Annals of Discrete Mathematics, 46 (1991), North Holland Publishing Co.: North Holland Publishing Co., Amsterdam · Zbl 0715.00010
[14] Diestel, R., Graph Theory (2000), Springer: Springer, New York · Zbl 0957.05001
[15] Falcón, R. M., Decomposition of principal autotopisms into triples of a Latin square, 95-98 (2006)
[16] Falcón, R. M., Latin squares associated to principal autotopisms of long cycles. Application in cryptography, 213-230 (2006) · Zbl 1203.05022
[17] Falcón, R. M., Cycle structures of autotopisms of the Latin squares of order up to 11, Ars Comb., 103, 239-256 (2012) · Zbl 1265.05077
[18] Falcón, R. M., The set of autotopisms of partial Latin squares, Discrete Math., 313, 1150-1161 (2013) · Zbl 1277.05024 · doi:10.1016/j.disc.2011.11.013
[19] Falcón, R. M.; Martín-Morales, J., Gröbner bases and the number of Latin squares related to autotopisms of order 7, J. Symbolic Comput., 42, 1142-1154 (2007) · Zbl 1129.05007 · doi:10.1016/j.jsc.2007.07.004
[20] Falcón, R. M.; Stones, R. J., Classifying partial Latin rectangles, Electron. Notes Discrete Math., 49, 765-771 (2015) · Zbl 1346.05021 · doi:10.1016/j.endm.2015.06.103
[21] Falcón, R. M.; Stones, R. J., Partial Latin rectangle graphs and autoparatopism groups of partial Latin rectangles with trivial autotopism groups, Discrete Math., 340, 1242-1260 (2017) · Zbl 1422.05027 · doi:10.1016/j.disc.2017.01.002
[22] Gardner, M., Mathematical games, Scientific American, 244, 4, 18-26 · doi:10.1038/scientificamerican0481-18
[23] Harary, F., Graph Theory (1969), Addison Wesley: Addison Wesley, Reading, Mass. · Zbl 0182.57702
[24] Hulpke, A.; Kaski, P.; Östergård, P. R.J., The number of Latin squares of order 11, Math. Comp., 80, 1197-1219 (2011) · Zbl 1210.05017 · doi:10.1090/S0025-5718-2010-02420-2
[25] Kerby, B.; Smith, J. D.H., Quasigroup automorphisms and symmetric group characters, Comment. Math. Univ. Carolin., 51, 279-286 (2010) · Zbl 1211.20063
[26] Kierstead, H. A., A simple competitive graph coloring algorithm, J. Comb. Theory B, 78, 57-68 (2000) · Zbl 1024.05029 · doi:10.1006/jctb.1999.1927
[27] Kierstead, H. A., Asymmetric graph coloring games, J. Graph Theory, 48, 169-185 (2005) · Zbl 1116.91028 · doi:10.1002/jgt.20049
[28] Mckay, B. D.; Meynert, A.; Myrvold, W., Small Latin Squares, Quasigroups and Loops, J. Combin. Des., 15, 98-119 (2007) · Zbl 1112.05018 · doi:10.1002/jcd.20105
[29] Mckay, B. D.; Wanless, I. M., On the number of Latin Squares, Ann. Comb., 9, 335-344 (2005) · Zbl 1073.05013 · doi:10.1007/s00026-005-0261-7
[30] Mckay, B. D.; Wanless, I. M.; Zhang, X., The order of automorphisms of quasigroups, J. Combin. Des., 23, 275-288 (2015) · Zbl 1327.05043 · doi:10.1002/jcd.21389
[31] Mendis, M. J.L.; Wanless, I. M., Autoparatopisms of quasigroups and Latin squares, J. Combin. Des., 25, 51-74 (2017) · Zbl 1362.05027 · doi:10.1002/jcd.21515
[32] Sade, A. A., Autotopies des quasigroupes et des systèmes associatives, Arch. Math., 4, 1-23 (1968) · Zbl 0211.33201
[33] Schlund, M., Graph decompositions, Latin squares, and games (2011), TU München
[34] Smith, J. D.H., Homotopies of central quasigroups, Comm. Algebra, 40, 1878-1885 (2012) · Zbl 1252.20067 · doi:10.1080/00927872.2011.560133
[35] Stones, D. S.; Vojtěchovský, P.; Wanless, I. M., Cycle structure of autotopisms of quasigroups and Latin squares, J. Combin. Des., 20, 227-263 (2012) · Zbl 1248.05023 · doi:10.1002/jcd.20309
[36] Stones, R. J.; Su, M.; Liu, X.; Wang, G.; Lin, S., A Latin square autotopism secret sharing scheme, Des. Codes Cryptogr., 80, 635-650 (2016) · Zbl 1347.05023 · doi:10.1007/s10623-015-0123-1
[37] Wanless, I. M.; Ihrig, E. C., Symmetries that Latin squares inherit from 1-factorizations, J. Combin. Des., 13, 157-172 (2005) · Zbl 1067.05061 · doi:10.1002/jcd.20045
[38] Yan, M.; Feng, J.; Kong, Y.; Stones, R. J.; Marbach, T. G.; Wang, G.; Liu, X.; Su, M., LS-Blockchain: A Resilient Multi-cloud Storage Scheme via Latin Square Autotopisms and a Blockchain (2018)
[39] Zhu, X., Refined activation strategy for the marking game, J. Comb. Theory B, 98, 1-18 (2008) · Zbl 1127.05047 · doi:10.1016/j.jctb.2007.04.004
[40] Zhu, X., Game coloring the Cartesian product of graphs, J. Graph Theory, 59, 261-278 (2008) · Zbl 1223.05091 · doi:10.1002/jgt.20338
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.