Can colour-blind distinguish colour palettes? (Q396838)

Summary: Let \(c:E(G)\rightarrow [k]\) be a colouring, not necessarily proper, of edges of a graph \(G\). For a vertex \(v\in V\), let \(\overline{c}(v)=(a_1,\ldots,a_k)\), where \( a_i =|\{u:uv\in E(G),\;c(uv)=i\}|\), for \(i\in [k].\) If we re-order the sequence \(\overline{c}(v)\) non-decreasingly, we obtain a sequence \(c^*(v)=(d_1,\ldots,d_k)\), called a palette of a vertex \(v\). This can be viewed as the most comprehensive information about colours incident with \(v\) which can be delivered by a person who is unable to name colours but distinguishes one from another. The smallest \(k\) such that \(c^*\) is a proper colouring of vertices of \(G\) is called the colour-blind index of a graph \(G\), and is denoted by dal\((G)\). We conjecture that there is a constant \(K\) such that dal\((G)\leq K\) for every graph \(G\) for which the parameter is well defined. As our main result we prove that \(K\leq 6\) for regular graphs of sufficiently large degree, and for irregular graphs with \(\delta (G)\) and \(\Delta(G)\) satisfying certain conditions. The proofs are based on the Lopsided Lovász Local Lemma. We also show that \(K=3\) for all regular bipartite graphs, and for complete graphs of order \(n\geq 8\).