Previous |  Up |  Next


complete vertex colouring; achromatic number; Cartesian product; complete graph
The achromatic number of a graph $G$ is the maximum number of colours in a proper vertex colouring of $G$ such that for any two distinct colours there is an edge of $G$ incident with vertices of those two colours. We determine the achromatic number of the Cartesian product of $K_5$ and $K_n$ for all $n \le 24$.
[1] A.  Bouchet: Indice achromatique des graphes multiparti complets et réguliers. Cahiers Centre Études Rech. Opér. 20 (1978), 331–340. MR 0543176 | Zbl 0404.05026
[2] N. P.  Chiang and H. L.  Fu: On the achromatic number of the Cartesian product $G_1\times G_2$. Australas. J.  Combin. 6 (1992), 111–117. MR 1196112
[3] N. P.  Chiang and H. L. Fu: The achromatic indices of the regular complete multipartite graphs. Discrete Math. 141 (1995), 61–66. DOI 10.1016/0012-365X(93)E0207-K | MR 1336673
[4] K.  Edwards: The harmonious chromatic number and the achromatic number. In: Surveys in Combinatorics 1997. London Math. Soc. Lect. Notes Series 241, R. A. Bailey (ed.), Cambridge University Press, 1997, pp. 13–47. MR 1477743 | Zbl 0882.05062
[5] F.  Harary, S.  Hedetniemi and G.  Prins: An interpolation theorem for graphical homomorphisms. Portug. Math. 26 (1967), 454–462. MR 0272662
[6] M. Horňák and Š. Pčola: Achromatic number of $K_5\times K_n$ for large  $n$. Discrete Math. 234 (2001), 159–169. DOI 10.1016/S0012-365X(00)00399-X
[7] M.  Horňák and J. Puntigán: On the achromatic number of $K_m\times K_n$. In: Graphs and Other Combinatorial Topics. Proceedings of the Third Czechoslovak Symposium on Graph Theory, Prague, August 24–27, 1982, M.  Fiedler (ed.), Teubner, Leipzig, 1983, pp. 118–123. MR 0737024
[8] M.  Yannakakis and F.  Gavril: Edge dominating sets in graphs. SIAM J.  Appl. Math. 38 (1980), 364–372. DOI 10.1137/0138030 | MR 0579424
Partner of
EuDML logo