Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

Request Permissions   Purchase Content 
 
 

 

The chromatic number of the square of the $ 8$-cube


Authors: Janne I. Kokkala and Patric R. J. Östergård
Journal: Math. Comp.
MSC (2010): Primary 05C15; Secondary 94B25
DOI: https://doi.org/10.1090/mcom/3291
Published electronically: December 22, 2017
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: 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.


References [Enhancements On Off] (What's this?)

  • [1] M. R. Best, Binary codes with a minimum distance of four, IEEE Trans. Inform. Theory 26 (1980), no. 6, 738-742. MR 596287, https://doi.org/10.1109/TIT.1980.1056269
  • [2] M. R. Best and A. E. Brouwer, The triply shortened binary Hamming code is optimal, Discrete Math. 17 (1977), no. 3, 235-245. MR 0441537, https://doi.org/10.1016/0012-365X(77)90158-3
  • [3] M. R. Best, A. E. Brouwer, F. Jessie MacWilliams, Andrew M. Odlyzko, and Neil J. A. Sloane, Bounds for binary codes of length less than $ 25$, IEEE Trans. Infomation Theory IT-24 (1978), no. 1, 81-93. MR 0479645
  • [4] Tomáš Dvořák, Ivan Havel, Jean-Marie Laborde, and Petr Liebl, Generalized hypercubes and graph embedding with dilation, Proceedings of the 7th Fischland Colloquium, II (Wustrow, 1988), 1990, pp. 13-20. MR 1090602
  • [5] Frank Harary, Four difficult unsolved problems in graph theory, Recent advances in graph theory (Proc. Second Czechoslovak Sympos., Prague, 1974) Academia, Prague, 1975, pp. 249-256. MR 0382042
  • [6] Tommy R. Jensen and Bjarne Toft, Graph Coloring Problems, Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., New York, 1995. A Wiley-Interscience Publication. MR 1304254
  • [7] Petteri Kaski and Patric R. J. Östergård, Classification Algorithms for Codes and Designs, Algorithms and Computation in Mathematics, vol. 15, Springer-Verlag, Berlin, 2006. With 1 DVD-ROM (Windows, Macintosh and UNIX). MR 2192256
  • [8] 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] Dongsoo S. Kim, Ding-Zhu Du, and Panos M. Pardalos, A coloring problem on the $ n$-cube, Discrete Appl. Math. 103 (2000), no. 1-3, 307-311. MR 1762219, https://doi.org/10.1016/S0166-218X(99)00249-8
  • [10] Antti Laaksonen and Patric R. J. Östergård, Constructing error-correcting binary codes using transitive permutation groups, Discrete Appl. Math. 233 (2017), 65-70. MR 3711970
  • [11] J. Lauri, The square of the 9-hypercube is 14-colorable, preprint, available at http://arxiv.org/abs/1605.07613.
  • [12] Nathan Linial, Roy Meshulam, and Michael Tarsi, Matroidal bijections between graphs, J. Combin. Theory Ser. B 45 (1988), no. 1, 31-44. MR 953893, https://doi.org/10.1016/0095-8956(88)90053-6
  • [13] Brendan D. McKay and Adolfo Piperno, Practical graph isomorphism, II, J. Symbolic Comput. 60 (2014), 94-112. MR 3131381, https://doi.org/10.1016/j.jsc.2013.09.003
  • [14] Hung Quang Ngo, Ding-Zhu Du, and Ronald L. Graham, New bounds on a hypercube coloring problem, Inform. Process. Lett. 84 (2002), no. 5, 265-269. MR 1931730
  • [15] S. Niskanen and P. R. J. Östergård, Cliquer User's Guide, Version 1.0, Tech. Report T48, Communications Laboratory, Helsinki University of Technology, Espoo, 2003.
  • [16] Patric R. J. Östergård, On a hypercube coloring problem, J. Combin. Theory Ser. A 108 (2004), no. 2, 199-204. MR 2098840, https://doi.org/10.1016/j.jcta.2004.06.010
  • [17] Patric R. J. Östergård, On the size of optimal three-error-correcting binary codes of length 16, IEEE Trans. Inform. Theory 57 (2011), no. 10, 6824-6826. MR 2882264, https://doi.org/10.1109/TIT.2011.2144955
  • [18] Patric R. J. Östergård, Tsonka Baicheva, and Emil Kolev, Optimal binary one-error-correcting codes of length $ 10$ have $ 72$ codewords, IEEE Trans. Inform. Theory 45 (1999), no. 4, 1229-1231. MR 1686256, https://doi.org/10.1109/18.761273
  • [19] Charles Payan, On the chromatic number of cube-like graphs, Discrete Math. 103 (1992), no. 3, 271-277. MR 1171780, https://doi.org/10.1016/0012-365X(92)90319-B
  • [20] J. G. Rix, Hypercube coloring and the structure of binary codes, Master's thesis, The University of British Columbia, 2008.
  • [21] Joseph J. Rotman, An Introduction to the Theory of Groups, 4th ed., Graduate Texts in Mathematics, vol. 148, Springer-Verlag, New York, 1995. MR 1307623
  • [22] Peng-Jun Wan, Near-optimal conflict-free channel set assignments for an optical cluster-based hypercube network, J. Comb. Optim. 1 (1997), no. 2, 179-186. MR 1606905, https://doi.org/10.1023/A:1009759916586
  • [23] Günter M. Ziegler, Coloring Hamming graphs, optimal binary codes, and the $ 0/1$-Borsuk problem in low dimensions, Computational Discrete Mathematics, Lecture Notes in Comput. Sci., vol. 2122, Springer, Berlin, 2001, pp. 159-171. MR 1911588, https://doi.org/10.1007/3-540-45506-X_12

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 05C15, 94B25

Retrieve articles in all journals with MSC (2010): 05C15, 94B25


Additional Information

Janne I. Kokkala
Affiliation: Aalto University, School of Electrical Engineering, Department of Communications and Networking, P.O. Box 13000, 00076 Aalto, Finland
Email: janne.kokkala@aalto.fi

Patric R. J. Östergård
Affiliation: Aalto University, School of Electrical Engineering, Department of Communications and Networking, P.O. Box 13000, 00076 Aalto, Finland
Email: patric.ostergard@aalto.fi

DOI: https://doi.org/10.1090/mcom/3291
Received by editor(s): December 2, 2016
Received by editor(s) in revised form: April 15, 2017
Published electronically: December 22, 2017
Additional Notes: The work of the first author was supported by Aalto ELEC Doctoral School, Nokia Foundation, Emil Aaltonen Foundation, and by Academy of Finland Project 289002
The work of the second author was supported in part by Academy of Finland Project 289002.
Article copyright: © Copyright 2017 American Mathematical Society

American Mathematical Society