Colour-blind can distinguish colour pallets

Jakub Przybyło¹

¹AGH University of Science and Technology, al. A. Mickiewicza 30, 30-059 Krakow, Poland

The electronic journal of combinatorics, Tome 21 (2014) no. 2

Résumé

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).

Détail

DOI : 10.37236/3744

Classification : 05C15, 05C40
Mots-clés : neighbour-distinguishing colouring, colour pallet, colour-blind person