Opuscula Math. 41, no. 2 (2021), 163-185
https://doi.org/10.7494/OpMath.2021.41.2.163
Opuscula Mathematica
The achromatic number of K6 □ K7 is 18
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.
- A. Bouchet, Indice achromatique des graphes multiparti complets et réguliers, Cahiers du Centre d'Études de Recherche Opérationelle 20 (1978), 331-340.
- 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.
- N.P. Chiang, H.L. Fu, The achromatic indices of the regular complete multipartite graphs, Discrete Math. 141 (1995), 61-66.
- F. Harary, S. Hedetniemi, G. Prins, An interpolation theorem for graphical homomorphisms, Portug. Math. 26 (1967), 454-462.
- 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].
- M. Horňák, The achromatic number of the Cartesian product of \(K_6\) and \(K_q\), arXiv:2009.07521v1 [math.CO].
- M. Horňák, Š. Pčola, Achromatic number of \(K_5\times K_n\) for large \(n\), Discrete Math. 234 (2001), 159-169.
- M. Horňák, Š. Pčola, Achromatic number of \(K_5\times K_n\) for small \(n\), Czechoslovak Math. J. 53 (128) (2003), 963-988.
- 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.
- W. Imrich, S. Klavžar, Product Graphs, Wiley-Interscience, New York, 2000.
- Mirko Horňák
https://orcid.org/0000-0002-3588-8455- P.J. Šafárik University, Institute of Mathematics, Jesenná 5, 040 01 Košice, Slovakia
- Communicated by Adam Paweł Wojda.
- Received: 2020-09-18.
- Revised: 2021-01-06.
- Accepted: 2021-01-27.
- Published online: 2021-03-17.
