Distinguishing coloring

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.

"[1] This example is solved by using a distinguishing coloring for a cycle graph.

Therefore, the distinguishing number of the complete graph Kn is n. However, the graph obtained from Kn by attaching a degree-one vertex to each vertex of Kn has a significantly smaller distinguishing number, despite having the same symmetry group: it has a distinguishing coloring with

For instance, every two-coloring of a five-cycle has a reflection symmetry.

However, every hypercube graph of higher dimension has distinguishing number only two.

[7][8][9] The exact complexity of computing distinguishing numbers is unclear, because it is closely related to the still-unknown complexity of graph isomorphism.

[10] Additionally, testing whether the distinguishing chromatic number is at most three is NP-hard,[9] and testing whether it is at most two is "at least as hard as graph automorphism, but no harder than graph isomorphism".

The minimum number of colors in a proper distinguishing coloring of a graph is called the distinguishing chromatic number of the graph.