Opuscula Math. 41, no. 2 (2021), 163-185

Opuscula Mathematica

The achromatic number of K6 □ K7 is 18

Mirko Horňák

Abstract. A vertex colouring \(f:V(G)\to C\) of a graph \(G\) is complete if for any two distinct colours \(c_1, c_2 \in C\) there is an edge \(\{v_1,v_2\}\in E(G)\) such that \(f(v_i)=c_i\), \(i=1,2\). The achromatic number of \(G\) is the maximum number \(\text{achr}(G)\) of colours in a proper complete vertex colouring of \(G\). In the paper it is proved that \(\text{achr}(K_6 \square K_7)=18\). This result finalises the determination of \(\text{achr}(K_6 \square K_q)\).

Keywords: complete vertex colouring, achromatic number, Cartesian product.

Mathematics Subject Classification: 05C15.

Full text (pdf)

  1. A. Bouchet, Indice achromatique des graphes multiparti complets et réguliers, Cahiers du Centre d'Études de Recherche Opérationelle 20 (1978), 331-340.
  2. N.P. Chiang, H.L. Fu, On the achromatic number of the Cartesian product \(G_1\times G_2\), Australas. J. Combin. 6 (1992), 111-117.
  3. N.P. Chiang, H.L. Fu, The achromatic indices of the regular complete multipartite graphs, Discrete Math. 141 (1995), 61-66.
  4. F. Harary, S. Hedetniemi, G. Prins, An interpolation theorem for graphical homomorphisms, Portug. Math. 26 (1967), 454-462.
  5. M. Horňák, The achromatic number of \(K_6 \square K_q\) equals \(2q+3\) if \(q \geq 41\) is odd, arXiv:2009.06955v1 [math.CO].
  6. M. Horňák, The achromatic number of the Cartesian product of \(K_6\) and \(K_q\), arXiv:2009.07521v1 [math.CO].
  7. M. Horňák, Š. Pčola, Achromatic number of \(K_5\times K_n\) for large \(n\), Discrete Math. 234 (2001), 159-169.
  8. M. Horňák, Š. Pčola, Achromatic number of \(K_5\times K_n\) for small \(n\), Czechoslovak Math. J. 53 (128) (2003), 963-988.
  9. M. Horňák, J. Puntigán, On the Achromatic Number of \(K_m\times K_n\), [in:] M. Fiedler (ed.), Graphs and Other Combinatorial Topics, Teubner, Leipzig, 1983, 118-123.
  10. W. Imrich, S. Klavžar, Product Graphs, Wiley-Interscience, New York, 2000.
  • Communicated by Adam Paweł Wojda.
  • Received: 2020-09-18.
  • Revised: 2021-01-06.
  • Accepted: 2021-01-27.
  • Published online: 2021-03-17.
Opuscula Mathematica - cover

Cite this article as:
Mirko Horňák, The achromatic number of K6 □ K7 is 18, Opuscula Math. 41, no. 2 (2021), 163-185, https://doi.org/10.7494/OpMath.2021.41.2.163

Download this article's citation as:
a .bib file (BibTeX),
a .ris file (RefMan),
a .enw file (EndNote)
or export to RefWorks.

In accordance with EU legislation we advise you this website uses cookies to allow us to see how the site is used. All data is anonymized.
All recent versions of popular browsers give users a level of control over cookies. Users can set their browsers to accept or reject all, or certain, cookies.