The achromatic number of k6 □ k7 is 18

• Autorzy: Horńak Mirko

Identyfikatory

DOI

10.7494/OpMath.2021.41.2.163

• Języki publikacji: EN

Abstrakty

EN

A vertex colouring ƒ: V(G) ⇾ C of a graph G is complete if for any two distinct colours c 1 ,c2 ∈ C there is an edge {v 1 ,v2} ∈ E(G) such that ƒ (vi) = ci, i = 1, 2. The achromatic number of G is the maximum number achr(G) of colours in a proper complete vertex colouring of G. In the paper it is proved that achr(K6 □ K7) = 18. This result finalises the determination of achr(K6 □ Kq).

Słowa kluczowe

EN

complete vertex colouring; achromatic number; Cartesian product

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2021
• Tom: Vol. 41, no. 2
• Strony: 163--185
• Opis fizyczny: BIbliogr. 10 poz.

Twórcy

autor

Horńak Mirko

• P.J. Safarik University Institute of Mathematics Jesenna 5, 040 01 Kosice, Slovakia

Bibliografia

• [1] A. Bouchet, Indice achromatique des graphes multiparti complets et reguliers, Cahiers du Centre d’Etudes de Recherche Operationelle 20 (1978), 331-340.
• [2] N.P. Chiang, H.L. Fu, On the achromatic number of the Cartesian product G 1 x G2, Australas. J. Combin. 6 (1992), 111-117.
• [3] N.P. Chiang, H.L. Fu, The achromatic indices of the regular complete multipartite graphs, Discrete Math. 141 (1995), 61-66.
• [4] F. Harary, S. Hedetniemi, G. Prins, An interpolation theorem for graphical homomorphisms, Portug. Math. 26 (1967), 454-462.
• [5] M. Horńak, The achromatic number of K6 □ Kq equals 2q + 3 if q > 41 is odd, arXiv:2009.06955v1 [math.CO].
• [6] M. Horńak, The achromatic number of the Cartesian product of K6 and Kq, arXiv:2009.07521v1 [math.CO].
• [7] M. Horńak, S. Pcola, Achromatic number of K5 x Kn for large n, Discrete Math. 234 (2001), 159-169.
• [8] M. Horńak, S. Pcola, Achromatic number of K5 x Kn for small n, Czechoslovak Math. J. 53 (128) (2003), 963-988.
• [9] M. Horńak, J. Puntigan, On the Achromatic Number of Km x Kn , [in:] M. Fiedler (ed.), Graphs and Other Combinatorial Topics, Teubner, Leipzig, 1983, 118-123.
• [10] W. Imrich, S. Klavzar, Product Graphs, Wiley-Interscience, New York, 2000.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2021).