| Title:
|
Achromatic number of $K_5 \times K_n$ for small $n$ (English) |
| Author:
|
Horňák, Mirko |
| Author:
|
Pčola, Štefan |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
53 |
| Issue:
|
4 |
| Year:
|
2003 |
| Pages:
|
963-988 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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$. (English) |
| Keyword:
|
complete vertex colouring |
| Keyword:
|
achromatic number |
| Keyword:
|
Cartesian product |
| Keyword:
|
complete graph |
| MSC:
|
05C15 |
| idZBL:
|
Zbl 1080.05510 |
| idMR:
|
MR2018843 |
| . |
| Date available:
|
2009-09-24T11:08:18Z |
| Last updated:
|
2020-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/127853 |
| . |
| Reference:
|
[1] A. Bouchet: Indice achromatique des graphes multiparti complets et réguliers.Cahiers Centre Études Rech. Opér. 20 (1978), 331–340. Zbl 0404.05026, MR 0543176 |
| Reference:
|
[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 |
| Reference:
|
[3] N. P. Chiang and H. L. Fu: The achromatic indices of the regular complete multipartite graphs.Discrete Math. 141 (1995), 61–66. MR 1336673, 10.1016/0012-365X(93)E0207-K |
| Reference:
|
[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. Zbl 0882.05062, MR 1477743 |
| Reference:
|
[5] F. Harary, S. Hedetniemi and G. Prins: An interpolation theorem for graphical homomorphisms.Portug. Math. 26 (1967), 454–462. MR 0272662 |
| Reference:
|
[6] M. Horňák and Š. Pčola: Achromatic number of $K_5\times K_n$ for large $n$.Discrete Math. 234 (2001), 159–169. MR 1826830, 10.1016/S0012-365X(00)00399-X |
| Reference:
|
[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 |
| Reference:
|
[8] M. Yannakakis and F. Gavril: Edge dominating sets in graphs.SIAM J. Appl. Math. 38 (1980), 364–372. MR 0579424, 10.1137/0138030 |
| . |
