Can colour-blind distinguish colour palettes? (Q396838): Difference between revisions
From MaRDI portal
Changed an Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(2 intermediate revisions by 2 users not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A simpler counterexample to the reconstruction conjecture for denumerable graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Vertex colouring edge partitions / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q2784326 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Lopsided Lovász Local lemma and Latin transversals / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Edge weights and vertex colours / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 22:15, 8 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Can colour-blind distinguish colour palettes? |
scientific article |
Statements
Can colour-blind distinguish colour palettes? (English)
0 references
14 August 2014
0 references
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\).
0 references
graph colouring
0 references
distinguishing adjacent vertices
0 references
Lovász local lemma
0 references