The achromatic number of K₆\square K₇ is 18

2020/09/17 by Mirko Horňák, Hornak, Mirko
Computer Science · Mathematics · #05C15 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2009.08117

openalex publication_date 2020/09/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

A vertex colouring f:V(G)→ C of a graph G is complete if for any two distinct colours c₁,c₂∈ C there is an edge \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 achr(K₆\square K₇)=18. This result finalises the determination of achr(K₆\square K_q).

Related

• The achromatic number of the Cartesian product of K₆ and K_q
• The achromatic number of K₆\square K_q equals 2q+3 if q≥41 is odd
• On the achromatic number of the Cartesian product of two complete graphs
• Achromatic arboricity on complete graphs
• Chromatic Completion Number