Geodesic
The achromatic number of $K_6\square K_q$ equals $2q+3$ if $q\ge41$ is odd
Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 4, pp. 1103-1121 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

Let G be a graph and C a finite set of colours. A vertex colouring f:V(G)→ C is complete provided that for any two distinct colours c_1,c_2∈ C there is v_1v_2∈ E(G) such that f(v_i)=c_i, i=1,2. The achromatic number of G is the maximum number of colours in a proper complete vertex colouring of G. In the paper it is proved that if q≥41 is an odd integer, then the achromatic number of the Cartesian product of K_6 and K_q is 2q+3.
Keywords: complete vertex colouring, achromatic number, Cartesian product, complete graph 
@article{DMGT_2023_43_4_a12,
     author = {Hor\v{n}\'ak, Mirko},
     title = {The achromatic number of $K_6\square K_q$ equals $2q+3$ if $q\ge41$ is odd},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {1103--1121},
     year = {2023},
     volume = {43},
     number = {4},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2023_43_4_a12/}
}
TY  - JOUR
AU  - Horňák, Mirko
TI  - The achromatic number of $K_6\square K_q$ equals $2q+3$ if $q\ge41$ is odd
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2023
SP  - 1103
EP  - 1121
VL  - 43
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/DMGT_2023_43_4_a12/
LA  - en
ID  - DMGT_2023_43_4_a12
ER  - 
%0 Journal Article
%A Horňák, Mirko
%T The achromatic number of $K_6\square K_q$ equals $2q+3$ if $q\ge41$ is odd
%J Discussiones Mathematicae. Graph Theory
%D 2023
%P 1103-1121
%V 43
%N 4
%U http://geodesic.mathdoc.fr/item/DMGT_2023_43_4_a12/
%G en
%F DMGT_2023_43_4_a12
Horňák, Mirko. The achromatic number of $K_6\square K_q$ equals $2q+3$ if $q\ge41$ is odd. Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 4, pp. 1103-1121. http://geodesic.mathdoc.fr/item/DMGT_2023_43_4_a12/

[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. Cairnie and K.J. Edwards, The achromatic number of bounded degree trees, Discrete Math. 188 (1998) 87–97. https://doi.org/10.1016/S0012-365X(97)00278-1

[3] G. Chartrand and P. Zhang, Chromatic Graph Theory, 2nd Ed. (Chapman and Hall/CRC, Boca Raton, 2009). https://doi.org/10.1201/9780429438868

[4] N.-P. Chiang and H.-L. Fu, On the achromatic number of the Cartesian product G1× G2, Australas. J. Combin. 6 (1992) 111–117.

[5] N.-P. Chiang and H.-L. Fu, The achromatic indices of the regular complete multipartite graphs, Discrete Math. 141 (1995) 61–66. https://doi.org/10.1016/0012-365X(93)E0207-K

[6] K.J. Edwards, The harmonious chromatic number and the achromatic number, in: Surveys in Combinatorics (Invited papers for 16th British Combinatorial Conference, R.A. Bailey (Ed(s)), (Cambridge University Press, Cambridge 1997) 13–47.

[7] K.J. Edwards, A bibliography of harmonious colourings and achromatic number. http://staff.computing.dundee.ac.uk/kedwards/biblio.html

[8] F. Harary, S. Hedetniemi and G. Prins, An interpolation theorem for graphical homomorphisms, Port. Math. 26 (1967) 454–462.

[9] P. Hell and D.J. Miller, Achromatic numbers and graph operations, Discrete Math. 108 (1992) 297–305. https://doi.org/10.1016/0012-365X(92)90683-7

[10] F. Hughes and G. MacGillivray, The achromatic number of graphs: a survey and some new results, Bull. Inst. Combin. Appl. 19 (1997) 27–56.

[11] M. Horňák, The achromatic number of the Cartesian product of K6 and Kq. arXiv: 2009.07521v1 [math.CO]

[12] M. Horňák, The achromatic number of K6\square K7 is 18, Opuscula Math. 41 (2021) 163–185. https://doi.org/10.7494/OpMath.2021.41.2.163

[13] M. Horňák and Š. Pčola, Achromatic number of K5× Kn for large n, Discrete Math. 234 (2001) 159–169. https://doi.org/10.1016/S0012-365X(00)00399-X

[14] M. Horňák and Š. Pčola, Achromatic number of K5× Kn for small n, Czechoslovak Math. J. 53 (2003) 963–988. https://doi.org/10.1023/B:CMAJ.0000024534.51299.08

[15] M. Horňák and J. Puntigán, On the achromatic number of Km× Kn, in: Graphs and Other Combinatorial Topics, M. Fiedler (Ed(s)), (Teubner, Leipzig 1983) 118–123.

[16] W. Imrich and S. Klavžar, Product Graphs (Wiley-Interscience, New York, 2000).