On the Palette Index of Complete Bipartite Graphs

Abstract

The palette of a vertex x of a graph G determined by a proper edge colouring φ of G is the set {φ(xy) : xy ∈ E(G)} and the diversity of φ is the number of different palettes determined by φ. The palette index of G is the minimum of diversities of φ taken over all proper edge colourings φ of G. In the article we determine the palette index of Km,n for m ≤ 5 and pose two conjectures concerning the palette index of complete bipartite graphs.

Keywords

• edge colouring
• palette index
• bipartite graph
• 05c15