Metraipolis › archive › dc_91f3a182f830

Distinguishing coloring — Wikipedia (en)

Source
Wikipedia (en)
Original
https://en.wikipedia.org/wiki/Distinguishing_coloring
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-07T23:23:04.591Z
SHA-256 of the archived text
ce3ef83e965f243e0f06ce85d5afcb88c8822204a1c31aca9ee1c5ae92b20f1d
Stable URL of this page
https://metraipolis.com/documento/dc_91f3a182f830

How to cite

Distinguishing coloring — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Distinguishing_coloring (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_91f3a182f830 (Metraipolis archive dc_91f3a182f830, sha256 ce3ef83e965f243e0f06ce85d5afcb88c8822204a1c31aca9ee1c5ae92b20f1d)
BibTeX
@misc{dc91f3a182f830,
  title = {Distinguishing coloring — Wikipedia (en)},
  howpublished = {Wikipedia (en)},
  url = {https://en.wikipedia.org/wiki/Distinguishing_coloring},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_91f3a182f830; sha256 ce3ef83e965f243e0f06ce85d5afcb88c8822204a1c31aca9ee1c5ae92b20f1d},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Distinguishing_coloring. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

In graph theory, a distinguishing coloring or distinguishing labeling of a graph is an assignment of colors or labels to the vertices of the graph that destroys all of the nontrivial symmetries of the graph. The coloring does not need to be a proper coloring: adjacent vertices are allowed to be given the same color. For the colored graph, there should not exist any one-to-one mapping of the vertices to themselves that preserves both adjacency and coloring. The minimum number of colors in a distinguishing coloring is called the distinguishing number of the graph. Distinguishing colorings and distinguishing numbers were introduced by Albertson & Collins (1996), who provided the following motivating example, based on a puzzle previously formulated by Frank Rubin: "Suppose you have a ring of keys to different doors; each key only opens one door, but they all look indistinguishable to you. How few colors do you need, in order to color the handles of the keys in such a way that you can uniquely identify each key?" This example is solved by using a distinguishing coloring for a cycle graph. With such a coloring, each key will be uniquely identified by its color and the sequence of colors surrounding it.

Tema degli esploratori: matematica e informatica teorica (deposito sistematico; ricerca «graph theory»).
Fonte: Wikipedia in inglese, voce «Distinguishing coloring» — https://en.wikipedia.org/wiki/Distinguishing_coloring
Wikidata Q25304053 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q25304053
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Distinguishing_coloring?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 1335651868, consultata il 2026-10-07T23:02:11.429Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 4b09ad8a236e508cb981b9978b0ff1579a3980b3bada0776f7c6a25a3e165e2b