Article in volume
Authors:
Mirko Horňák
Department of Geometry and AlgebraP.J. Safárik University, Jesenná 5041 54 KOŠICE SLOVAKIA
email: mirko.hornak@upjs.sk
Title:
The achromatic number of the Cartesian product of $K_6$ and $K_q$
PDFSource:
Discussiones Mathematicae Graph Theory 44(2) (2024) 411-433
Received: 2021-07-18 , Revised: 2022-03-01 , Accepted: 2022-03-01 , Available online: 2022-03-12 , https://doi.org/10.7151/dmgt.2451
Abstract:
Let $G$ be a graph and $C$ a finite set of colours. A vertex colouring
$f:V(G)\to C$ is complete if for any pair of distinct colours $c_1,c_2\in C$
one can find 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 defined to be the maximum number achr$(G)$ of
colours in a proper complete vertex colouring of $G$. In the paper
achr$(K_6\square K_q)$ is determined for any integer $q$ such that either
$8\le q\le40$ or $q\ge42$ is even.
Keywords:
complete vertex colouring, achromatic number, Cartesian product, complete graph
References:
- A. Bouchet, Indice achromatique des graphes multiparti complets et réguliers, Cahiers Centre Études Rech. Opér. 20 (1978) 331–340.
- N.P. Chiang and H.L. Fu, On the achromatic number of the cartesian product $G_1× G_2$, Australas. J. Combin. 6 (1992) 111–117.
- F. Harary, S. Hedetniemi and G. Prins, An interpolation theorem for graphical homomorphisms, Port. Math. 26 (1967) {453–462}.
- M. Horňák, The achromatic number of $K_6\square K_q$ equals $2q+3$ if $q\ge41$ is odd, Discuss. Math. Graph Theory, in press.
https://doi.org/10.7151/dmgt.2420 - M. Horňák, The achromatic number of $K_6\square K_7$ is $18$, Opuscula Math. 41 (2021) 163–185.
https://doi.org/10.7494/OpMath.2021.41.2.163 - M. Horňák and Š. Pčola, Achromatic number of $K_5× K_n$ for small $n$, Czechoslovak Math. J. 53 (2003) 963–988.
https://doi.org/10.1023/B:CMAJ.0000024534.51299.08 - M. Horňák, J. Puntigán, On the achromatic number of $K_m× K_n$, in: Graphs and Other Combinatorial Topics, M. Fiedler (Ed(s)), (Teubner, Leipzig 1983) 118–123.
- W. Imrich and S. Klavžar, {Product Graphs: Structure and Recognition} (Wiley-Interscience, New York, 2000).
Close