The achromatic number of K₆\square K_q equals 2q+3 if q≥41 is odd

2020/09/15 by Hornak, Mirko
#05C15 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2009.06955

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 c₁,c₂∈ C there is v₁v₂∈ E(G) such that f(v_i)=c_i, 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 if q≥41 is an odd integer, then the achromatic number of the Cartesian product of K₆ and K_q is 2q+3.

Related

• The achromatic number of the Cartesian product of K₆ and K_q
• The achromatic number of K₆\square K₇ is 18
• On the achromatic number of the Cartesian product of two complete graphs
• Cartesian Product and Acyclic Edge Colouring
• Acyclic colourings of graphs with obstructions