DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2022): 1.9

SNIP (2022): 0.902

Discussiones Mathematicae Graph Theory

Article in volume

Authors:

M. Horňák

Mirko Horňák

Department of Geometry and AlgebraP.J. Safárik University, Jesenná 5041 54 KOŠICE SLOVAKIA

email: mirko.hornak@upjs.sk

0000-0002-3588-8455

Title:

The achromatic number of $K_6\square K_q$ equals 2q+3 if $q\ge41$ is odd

PDF

Source:

Discussiones Mathematicae Graph Theory 43(4) (2023) 1103-1121

Received: 2020-11-08 , Revised: 2021-06-29 , Accepted: 2021-06-29 , Available online: 2021-07-16 , https://doi.org/10.7151/dmgt.2420

Abstract:

Let $G$ be a graph and $C$ a finite set of colours. A vertex colouring $f:V(G)\to C$ is complete provided that for any two distinct colours $c_1,c_2\in C$ there is $v_1v_2\in 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\ge41$ 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

References:

  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 $G_1× G_2$, 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 $K_6$ and $K_q$.
    arXiv: 2009.07521v1 [math.CO]
  12. 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
  13. M. Horňák and Š. Pčola, Achromatic number of $K_5× K_n$ 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 $K_5× K_n$ 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 $K_m× K_n$, 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).
Close