×

The chromatic number of the square of the 8-cube. (English) Zbl 1387.05092

Summary: A cube-like graph is a Cayley graph for the elementary abelian group of order \(2^n\). In studies of the chromatic number of cube-like graphs, the \(k\)th power of the \(n\)-dimensional hypercube, \(Q_n^k\), is frequently considered. This coloring problem can be considered in the framework of coding theory, as the graph \(Q_n^k\) can be constructed with one vertex for each binary word of length \(n\) and edges between vertices exactly when the Hamming distance between the corresponding words is at most \(k\). Consequently, a proper coloring of \(Q_n^k\) corresponds to a partition of the \(n\)-dimensional binary Hamming space into codes with minimum distance at least \(k+1\). The smallest open case, the chromatic number of \(Q_8^2\), is here settled by finding a 13-coloring. Such 13-colorings with specific symmetries are further classified.

MSC:

05C15 Coloring of graphs and hypergraphs
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
94B25 Combinatorial codes
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Best, M. R., Binary codes with a minimum distance of four, IEEE Trans. Inform. Theory, 26, 6, 738-742 (1980) · Zbl 0466.94020
[2] Best, M. R.; Brouwer, A. E., The triply shortened binary Hamming code is optimal, Discrete Math., 17, 3, 235-245 (1977) · Zbl 0356.94009
[3] Best, M. R.; Brouwer, A. E.; MacWilliams, F. Jessie; Odlyzko, Andrew M.; Sloane, Neil J. A., Bounds for binary codes of length less than \(25\), IEEE Trans. Infomation Theory, IT-24, 1, 81-93 (1978) · Zbl 0369.94011
[4] Dvo\v r\'ak, Tom\'a\v s.; Havel, Ivan; Laborde, Jean-Marie; Liebl, Petr, Generalized hypercubes and graph embedding with dilation, Rostock. Math. Kolloq.. Proceedings of the 7th Fischland Colloquium, II (Wustrow, 1988), 39, 13-20 (1990) · Zbl 0719.05036
[5] Harary, Frank, Four difficult unsolved problems in graph theory. Recent advances in graph theory, Proc. Second Czechoslovak Sympos., Prague, 1974, 249-256 (1975), Academia, Prague
[6] Jensen, Tommy R.; Toft, Bjarne, Graph Coloring Problems, Wiley-Interscience Series in Discrete Mathematics and Optimization, xxii+295 pp. (1995), John Wiley & Sons, Inc., New York · Zbl 0855.05054
[7] Kaski, Petteri; \"Osterg\aa rd, Patric R. J., Classification Algorithms for Codes and Designs, Algorithms and Computation in Mathematics 15, xii+412 pp. (2006), Springer-Verlag, Berlin · Zbl 1089.05001
[8] KP08 P. Kaski and O. Pottonen, libexact user’s guide, version 1.0, Tech. Report TR 2008-1, Helsinki Institute for Information Technology HIIT, Helsinki, 2008.
[9] Kim, Dongsoo S.; Du, Ding-Zhu; Pardalos, Panos M., A coloring problem on the \(n\)-cube, Discrete Appl. Math., 103, 1-3, 307-311 (2000) · Zbl 0949.05024
[10] Laaksonen, Antti; \"Osterg\aa rd, Patric R. J., Constructing error-correcting binary codes using transitive permutation groups, Discrete Appl. Math., 233, 65-70 (2017) · Zbl 1403.94109
[11] L16 J. Lauri, The square of the 9-hypercube is 14-colorable, preprint, available at http://arxiv.org/abs/1605.07613.
[12] Linial, Nathan; Meshulam, Roy; Tarsi, Michael, Matroidal bijections between graphs, J. Combin. Theory Ser. B, 45, 1, 31-44 (1988) · Zbl 0724.05067
[13] McKay, Brendan D.; Piperno, Adolfo, Practical graph isomorphism, II, J. Symbolic Comput., 60, 94-112 (2014) · Zbl 1394.05079
[14] Ngo, Hung Quang; Du, Ding-Zhu; Graham, Ronald L., New bounds on a hypercube coloring problem, Inform. Process. Lett., 84, 5, 265-269 (2002) · Zbl 1042.68083
[15] NO03 S. Niskanen and P. R. J. \`“Ostergrd, Cliquer User”s Guide, Version 1.0, Tech. Report T48, Communications Laboratory, Helsinki University of Technology, Espoo, 2003.
[16] \"Osterg\aa rd, Patric R. J., On a hypercube coloring problem, J. Combin. Theory Ser. A, 108, 2, 199-204 (2004) · Zbl 1061.05035
[17] \"Osterg\aa rd, Patric R. J., On the size of optimal three-error-correcting binary codes of length 16, IEEE Trans. Inform. Theory, 57, 10, 6824-6826 (2011) · Zbl 1365.94527
[18] \"Osterg\aa rd, Patric R. J.; Baicheva, Tsonka; Kolev, Emil, Optimal binary one-error-correcting codes of length \(10\) have \(72\) codewords, IEEE Trans. Inform. Theory, 45, 4, 1229-1231 (1999) · Zbl 0958.94040
[19] Payan, Charles, On the chromatic number of cube-like graphs, Discrete Math., 103, 3, 271-277 (1992) · Zbl 0772.05043
[20] R08 J. G. Rix, Hypercube coloring and the structure of binary codes, Master’s thesis, The University of British Columbia, 2008.
[21] Rotman, Joseph J., An Introduction to the Theory of Groups, Graduate Texts in Mathematics 148, xvi+513 pp. (1995), Springer-Verlag, New York · Zbl 0810.20001
[22] Wan, Peng-Jun, Near-optimal conflict-free channel set assignments for an optical cluster-based hypercube network, J. Comb. Optim., 1, 2, 179-186 (1997) · Zbl 0883.68014
[23] Ziegler, G\"unter M., Coloring Hamming graphs, optimal binary codes, and the \(0/1\)-Borsuk problem in low dimensions. Computational Discrete Mathematics, Lecture Notes in Comput. Sci. 2122, 159-171 (2001), Springer, Berlin · Zbl 1004.52010
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.