Colour-blind can distinguish colour pallets (Q405211)

Summary: Let \(c:E\to\{1,\dots,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 \textit{L. Addario-Berry} [J. Comb. Theory, Ser. B 94, No. 2, 237--244 (2005; Zbl 1074.05031)].