On the achromatic number of the Cartesian product of two complete graphs

2022/07/03 by Horňák, Mirko
#05C15 (Primary) 51E20 (Secondary) #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2207.01023

Abstract

A vertex colouring f:V(G)→ C of a graph G is complete if for any c₁,c₂∈ C with c₁≠ c₂ there are in G adjacent vertices v₁,v₂ such that f(v₁)=c₁ and f(v₂)=c₂. The achromatic number of G is the maximum number achr(G) of colours in a proper complete vertex colouring of G. Let G₁\square G₂ denote the Cartesian product of graphs G₁ and G₂. In the paper achr(K_r²+r+1\square K_q) is determined for an infinite number of qs provided that r is a finite projective plane order.

Related

• The achromatic number of the Cartesian product of K₆ and K_q
• The achromatic number of K₆\square K₇ is 18
• The achromatic number of K₆\square K_q equals 2q+3 if q≥41 is odd
• Cartesian Product and Acyclic Edge Colouring
• Achromatic arboricity on complete graphs