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 K6Kq Equals 2q + 3 If q ≥ 41 is Odd

Published Online: 05 Aug 2021
Volume & Issue: AHEAD OF PRINT
Page range: -
Received: 08 Nov 2020
Accepted: 29 Jun 2021
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 provided that for any two distinct colours c1, c2C there is v1v2E(G) such that f(vi) = ci, 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 K6 and Kqis 2q + 3.

Keywords

MSC 2010

[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.Search in Google Scholar

[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-110.1016/S0012-365X(97)00278-1Search in Google Scholar

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

[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.Search in Google Scholar

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

[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.10.1017/CBO9780511662119.003Search in Google Scholar

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

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

[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-710.1016/0012-365X(92)90683-7Search in Google Scholar

[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.Search in Google Scholar

[11] M. Horňák, The achromatic number of the Cartesian product of K6and Kq. arXiv:2009.07521v1 [math.CO]Search in Google Scholar

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

[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-X10.1016/S0012-365X(00)00399-XSearch in Google Scholar

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

[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.Search in Google Scholar

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

Recommended articles from Trend MD

Plan your remote conference with Sciendo