Distinguishing coloring

In graph theory, a distinguishing coloring of a graph is an assignment of colors 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 previous puzzle 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.

Examples

Eight asymmetric graphs, each given a distinguishing coloring with only one color (red)

A graph has distinguishing number one if and only if it is asymmetric. For instance, the Frucht graph has a distinguishing coloring with only one color.

In a complete graph, the only distinguishing colorings assign a different color to each vertex. For, if two vertices were assigned the same color, there would exist a symmetry that swapped those two vertices, leaving the rest in place. Therefore, the distinguishing number of the complete graph K_n is n. However, the graph obtained from K_n by attaching a degree-one vertex to each vertex of K_n has a significantly smaller distinguishing number, despite having the same symmetry group: it has a distinguishing coloring with $\lceil {\sqrt {n}}\rceil$ colors, obtained by using a different ordered pair of colors for each pair of a vertex K_n and its attached neighbor.

For a cycle graph of three, four, or five vertices, three colors are needed to construct a distinguishing coloring. For instance, every two-coloring of a five-cycle has a reflection symmetry. In each of these cycles, assigning a unique color to each of two adjacent vertices and using the third color for all remaining vertices results in a three-color distinguishing coloring. However, cycles of six or more vertices have distinguishing colorings with only two colors.

Hypercube graphs exhibit a similar phenomenon to cycle graphs. The two- and three-dimensional hypercube graphs (the 4-cycle and the graph of a cube, respectively) have distinguishing number three. However, every hypercube graph of higher dimension has distinguishing number only two.

Computational complexity

The distinguishing numbers of planar graphs and interval graphs can be computed in polynomial time.

The exact complexity of computing distinguishing numbers is unclear, because it is closely related to the still-unknown complexity of graph isomorphism. However, it has been shown to belong to the complexity class AM. Additionally, testing whether the distinguishing number is at most three is NP-hard, and testing whether it is at most two is "at least as hard as graph automorphism, but no harder than graph isomorphism".

Additional properties

For every graph G, the distinguishing number of G is proportional to the logarithm of the number of automorphisms of G. If the automorphisms form a nontrivial abelian group, the distinguishing number is two, and if it forms a dihedral group then the distinguishing number is at most three.

For every finite group, there exists a graph with that group as its group of automorphisms, with distinguishing number two.

Variations

A proper distinguishing coloring is a distinguishing coloring that is also a proper coloring: each two adjacent vertices have different colors. The minimum number of colors in a proper distinguish coloring of a graph is called the distinguishing chromatic number of the graph.