Article
Full entry |
PDF
(0.4 MB)
Feedback
PDF
(0.4 MB)
Feedback
Keywords:
complete vertex colouring; achromatic number; Cartesian product; complete graph
complete vertex colouring; achromatic number; Cartesian product; complete graph
Summary:
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$.
References:
[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 | MR 1826830
[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
Search
Partner of
