1. bookAHEAD OF PRINT
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

The Achromatic Number of the Cartesian Product of K6 and Kq

Published Online: 22 Mar 2022
Volume & Issue: AHEAD OF PRINT
Page range: -
Received: 18 Jul 2021
Accepted: 01 Mar 2022
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
Abstract

Let G be a graph and C a finite set of colours. A vertex colouring f : V (G) → C is complete if for any pair of distinct colours c1, c2C one can find an edge {v1, v2} ∈ E(G) such that f(vi) = ci, 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(K6Kq) is determined for any integer q such that either 8 ≤ q ≤ 40 or q ≥ 42 is even.

Keywords

MSC 2010

[1] A. Bouchet, Indice achromatique des graphes multiparti complets et réguliers, Cahiers Centre Études Rech. Opér. 20 (1978) 331–340. Search in Google Scholar

[2] N.P. Chiang and H.L. Fu, On the achromatic number of the cartesian product G1 × G2, Australas. J. Combin. 6 (1992) 111–117. Search in Google Scholar

[3] F. Harary, S. Hedetniemi and G. Prins, An interpolation theorem for graphical homomorphisms, Port. Math. 26 (1967) 453–462. Search in Google Scholar

[4] M. Horňák, The achromatic number of K6Kq equals 2q + 3 if q ≥ 41 is odd, Discuss. Math. Graph Theory, in press. https://doi.org/10.7151/dmgt.242010.7151/dmgt.2420 Search in Google Scholar

[5] M. Horňák, The achromatic number of K6K7 is 18, Opuscula Math. 41 (2021) 163–185. https://doi.org/10.7494/OpMath.2021.41.2.16310.7494/OpMath.2021.41.2.163 Search in Google Scholar

[6] 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.0810.1023/B:CMAJ.0000024534.51299.08 Search in Google Scholar

[7] M. Horňák, 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. Search in Google Scholar

[8] W. Imrich and S. Klavžar, Product Graphs: Structure and Recognition (Wiley-Interscience, New York, 2000). Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo