Colour-blind Can Distinguish Colour Pallets

Abstract

Let $c:E\to\{1,\ldots,k\}$ be an edge colouring of a connected graph $G=(V,E)$. Each vertex $v$ is endowed with a naturally defined pallet under $c$, understood as the multiset of colours incident with $v$. If $\delta(G)\geq 2$, we obviously (for $k$ large enough) may colour the edges of $G$ so that adjacent vertices are distinguished by their pallets of colours. Suppose then that our coloured graph is examined by a person who is unable to name colours, but perceives if two object placed next to each other are coloured differently. Can we colour $G$ so that this individual can distinguish colour pallets of adjacent vertices? It is proved that if $\delta(G)$ is large enough, then it is possible using just colours 1, 2 and 3. This result is sharp and improves all earlier ones. It also constitutes a strengthening of a result by Addario-Berry, Aldred, Dalal and Reed (2005).