Distinguishing coloring

Last updated November 09, 2023

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?"^[1] 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.^[2]

Examples

Eight asymmetric graphs, each given a distinguishing coloring with only one color (red) Asym-graph.PNG — 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.^[3] 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.^[2]

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. That is, Frank Rubin's keyring puzzle requires three colors for rings of three, four or five keys, but only two colors for six or more keys or for two keys.^[2] For instance, in the ring of six keys shown, each key can be distinguished by its color and by the length or lengths of the adjacent blocks of oppositely-colored keys: there is only one key for each combination of key color and adjacent block lengths.

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.^[4]

The Petersen graph has distinguishing number 3. However other than this graph and the complete graphs, all Kneser graphs have distinguishing number 2.^[5] Similarly, among the generalized Petersen graphs, only the Petersen graph itself and the graph of the cube have distinguishing number 3; the rest have distinguishing number 2.^[6]

Computational complexity

The distinguishing numbers of trees, planar graphs, and interval graphs can be computed in polynomial time.^[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. However, it has been shown to belong to the complexity class AM.^[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".^[11]

Additional properties

A coloring of a given graph is distinguishing for that graph if and only if it is distinguishing for the complement graph. Therefore, every graph has the same distinguishing number as its complement.^[2]

For every graph $G$ , the distinguishing number of $G$ is at most 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.^[2]

For every finite group, there exists a graph with that group as its group of automorphisms, with distinguishing number two.^[2] This result extends Frucht's theorem that every finite group can be realized as the group of symmetries of a graph.

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.^[12]

Related Research Articles

In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph is named after Julius Petersen, who in 1898 constructed it to be the smallest bridgeless cubic graph with no three-edge-coloring.

In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices are of the same color; this is called a vertex coloring. Similarly, an edge coloring assigns a color to each edge so that no two adjacent edges are of the same color, and a face coloring of a planar graph assigns a color to each face or region so that no two faces that share a boundary have the same color.

In graph theory, a proper edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue, and green. Edge colorings are one of several different types of graph coloring. The edge-coloring problem asks whether it is possible to color the edges of a given graph using at most $k$ different colors, for a given value of $k$ , or with the fewest possible colors. The minimum required number of colors for the edges of a given graph is called the chromatic index of the graph. For example, the edges of the graph in the illustration can be colored by three colors but cannot be colored by two colors, so the graph shown has chromatic index three.

In graph theory, a branch of mathematics, list coloring is a type of graph coloring where each vertex can be restricted to a list of allowed colors. It was first studied in the 1970s in independent papers by Vizing and by Erdős, Rubin, and Taylor.

In graph theory, an exact coloring is a (proper) vertex coloring in which every pair of colors appears on exactly one pair of adjacent vertices. That is, it is a partition of the vertices of the graph into disjoint independent sets such that, for each pair of distinct independent sets in the partition, there is exactly one edge with endpoints in each set.

In graph theory, a subcoloring is an assignment of colors to a graph's vertices such that each color class induces a vertex disjoint union of cliques. That is, each color class should form a cluster graph.

In the mathematical field of graph theory, a snark is an undirected graph with exactly three edges per vertex whose edges cannot be colored with only three colors. In order to avoid trivial cases, snarks are often restricted to have additional requirements on their connectivity and on the length of their cycles. Infinitely many snarks exist.

In graph theory, a rook's graph is an undirected graph that represents all legal moves of the rook chess piece on a chessboard. Each vertex of a rook's graph represents a square on a chessboard, and there is an edge between any two squares sharing a row (rank) or column (file), the squares that a rook can move between. These graphs can be constructed for chessboards of any rectangular shape. Although rook's graphs have only minor significance in chess lore, they are more important in the abstract mathematics of graphs through their alternative constructions: rook's graphs are the Cartesian product of two complete graphs, and are the line graphs of complete bipartite graphs. The square rook's graphs constitute the two-dimensional Hamming graphs.

<span class="mw-page-title-main">Thue number</span>

In the mathematical area of graph theory, the Thue number of a graph is a variation of the chromatic index, defined by Alon et al. (2002) and named after mathematician Axel Thue, who studied the squarefree words used to define this number.

In the mathematical field of graph theory, a star coloring of a graph $G$ is a (proper) vertex coloring in which every path on four vertices uses at least three distinct colors. Equivalently, in a star coloring, the induced subgraphs formed by the vertices of any two colors has connected components that are star graphs. Star coloring has been introduced by Grünbaum (1973). The star chromatic number $of G is the fewest colors needed to star color G .$

In the study of graph coloring problems in mathematics and computer science, a greedy coloring or sequential coloring is a coloring of the vertices of a graph formed by a greedy algorithm that considers the vertices of the graph in sequence and assigns each vertex its first available color. Greedy colorings can be found in linear time, but they do not, in general, use the minimum number of colors possible.

In graph theory, an area of mathematics, an equitable coloring is an assignment of colors to the vertices of an undirected graph, in such a way that

In the mathematical field of graph theory, the Folkman graph is a 4-regular graph with 20 vertices and 40 edges. It is a regular bipartite graph with symmetries taking every edge to every other edge, but the two sides of its bipartition are not symmetric with each other, making it the smallest possible semi-symmetric graph. It is named after Jon Folkman, who constructed it for this property in 1967.

In the mathematical field of graph theory, the Clebsch graph is either of two complementary graphs on 16 vertices, a 5-regular graph with 40 edges and a 10-regular graph with 80 edges. The 80-edge graph is the dimension-5 halved cube graph; it was called the Clebsch graph name by Seidel (1968) because of its relation to the configuration of 16 lines on the quartic surface discovered in 1868 by the German mathematician Alfred Clebsch. The 40-edge variant is the dimension-5 folded cube graph; it is also known as the Greenwood–Gleason graph after the work of Robert E. Greenwood and Andrew M. Gleason (1955), who used it to evaluate the Ramsey number R(3,3,3) = 17.

Frucht's theorem is a theorem in algebraic graph theory conjectured by Dénes Kőnig in 1936 and proved by Robert Frucht in 1939. It states that every finite group is the group of symmetries of a finite undirected graph. More strongly, for any finite group G there exist infinitely many non-isomorphic simple connected graphs such that the automorphism group of each of them is isomorphic to G.

In graph theory, a branch of mathematics, the Hajós construction is an operation on graphs named after György Hajós (1961) that may be used to construct any critical graph or any graph whose chromatic number is at least some given threshold.

In graph theory, a branch of mathematics, the $k$ th power $G k$ of an undirected graph $G$ is another graph that has the same set of vertices, but in which two vertices are adjacent when their distance in $G$ is at most $k$ . Powers of graphs are referred to using terminology similar to that of exponentiation of numbers: $G 2$ is called the square of $G$ , $G 3$ is called the cube of $G$ , etc.

<span class="mw-page-title-main">Halved cube graph</span> Graph of the vertices and edges of a demihypercube

In graph theory, the halved cube graph or half cube graph of dimension $n$ is the graph of the demihypercube, formed by connecting pairs of vertices at distance exactly two from each other in the hypercube graph. That is, it is the half-square of the hypercube. This connectivity pattern produces two isomorphic graphs, disconnected from each other, each of which is the halved cube graph.

<span class="mw-page-title-main">Adjacent-vertex-distinguishing-total coloring</span> Type of total coloring in graph theory

In graph theory, a total coloring is a coloring on the vertices and edges of a graph such that:

In graph theory and computational complexity theory, a Frankl–Rödl graph is a graph defined by connecting pairs of vertices of a hypercube that are at a specified even distance from each other. The graphs of this type are parameterized by the dimension of the hypercube and by the distance between adjacent vertices.

References

↑ Rubin, Frank (1979), "Problem 729: the blind man's keys", Journal of Recreational Mathematics , 11: 128. Solution in vol. 12, 1980. As cited by Albertson & Collins (1996). Instead of using colors, Rubin phrased the problem in terms of key handles that could be distinguished from each other by touch. More precisely, this problem assumes that each key is symmetric, so that the keys cannot be distinguished from each other by their orientations on the keyring.
1 2 3 4 5 6 Albertson, Michael O.; Collins, Karen L. (1996), "Symmetry breaking in graphs", Electronic Journal of Combinatorics , 3 (1): R18, doi: 10.37236/1242 , MR 1394549 .
↑ See, e.g., Imrich, Wilfried; Klavžar, Sandi (2006), "Distinguishing Cartesian powers of graphs", Journal of Graph Theory , 53 (3): 250–260, CiteSeerX 10.1.1.59.9242 , doi:10.1002/jgt.20190, MR 2262268, S2CID 6808067, If a graph has no nontrivial automorphisms its distinguishing number is 1. In other words, $D (G) = 1$ for asymmetric graphs.
↑ Bogstad, Bill; Cowen, Lenore J. (2004), "The distinguishing number of the hypercube", Discrete Mathematics , 283 (1–3): 29–35, doi: 10.1016/j.disc.2003.11.018 , MR 2061481 .
↑ Albertson, Michael O.; Boutin, Debra L. (2007), "Using determining sets to distinguish Kneser graphs", Electronic Journal of Combinatorics , 14 (1): R20, doi: 10.37236/938 , MR 2285824 .
↑ Lal, A. K.; Bhattacharjya, B. (2009), "Breaking the symmetries of the book graph and the generalized Petersen graph", SIAM Journal on Discrete Mathematics , 23 (3): 1200–1216, doi:10.1137/080728640, MR 2538646 . Lal and Bhattacharjya (Theorem 4.3) credit this result to an unpublished masters thesis of K. S. Potanka (Virginia Polytechnic University, 1998).
↑ Cheng, Christine T. (2006), "On computing the distinguishing numbers of trees and forests", Electronic Journal of Combinatorics, 13 (1): R11, doi: 10.37236/1037 , MR 2200539 .
↑ Arvind, V.; Cheng, Christine T.; Devanur, Nikhil R. (2008), "On computing the distinguishing numbers of planar graphs and beyond: a counting approach", SIAM Journal on Discrete Mathematics , 22 (4): 1297–1324, arXiv: math/0703927 , doi:10.1137/07068686X, MR 2443115, S2CID 2402306 .
1 2 Cheng, Christine T. (2009), "On computing the distinguishing and distinguishing chromatic numbers of interval graphs and other results", Discrete Mathematics , 309 (16): 5169–5182, doi: 10.1016/j.disc.2009.04.004 , MR 2548918 .
↑ Russell, Alexander; Sundaram, Ravi (1998), "A note on the asymptotics and computational complexity of graph distinguishability", Electronic Journal of Combinatorics , 5: R23, doi: 10.37236/1361 , MR 1617449 .
↑ Eschen, Elaine M.; Hoàng, Chính T.; Sritharan, R.; Stewart, Lorna (2011), "On the complexity of deciding whether the distinguishing chromatic number of a graph is at most two", Discrete Mathematics , 311 (6): 431–434, arXiv: 0907.0691 , doi:10.1016/j.disc.2010.12.013, MR 2799894, S2CID 7679211 .
↑ Collins, Karen L.; Trenk, Ann N. (2006), "The distinguishing chromatic number", Electronic Journal of Combinatorics , 13 (1): R16, doi: 10.37236/1042 , MR 2200544 .

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Rubin, Frank (1979), "Problem 729: the blind man's keys", Journal of Recreational Mathematics , 11: 128. Solution in vol. 12, 1980. As cited by Albertson & Collins (1996). Instead of using colors, Rubin phrased the problem in terms of key handles that could be distinguished from each other by touch. More precisely, this problem assumes that each key is symmetric, so that the keys cannot be distinguished from each other by their orientations on the keyring.

[ac-2] 1 2 3 4 5 6 Albertson, Michael O.; Collins, Karen L. (1996), "Symmetry breaking in graphs", Electronic Journal of Combinatorics , 3 (1): R18, doi: 10.37236/1242 , MR 1394549 .

[3] See, e.g., Imrich, Wilfried; Klavžar, Sandi (2006), "Distinguishing Cartesian powers of graphs", Journal of Graph Theory , 53 (3): 250–260, CiteSeerX 10.1.1.59.9242 , doi:10.1002/jgt.20190, MR 2262268, S2CID 6808067, If a graph has no nontrivial automorphisms its distinguishing number is 1. In other words, $D (G) = 1$ for asymmetric graphs.

[4] Bogstad, Bill; Cowen, Lenore J. (2004), "The distinguishing number of the hypercube", Discrete Mathematics , 283 (1–3): 29–35, doi: 10.1016/j.disc.2003.11.018 , MR 2061481 .

[5] Albertson, Michael O.; Boutin, Debra L. (2007), "Using determining sets to distinguish Kneser graphs", Electronic Journal of Combinatorics , 14 (1): R20, doi: 10.37236/938 , MR 2285824 .

[6] Lal, A. K.; Bhattacharjya, B. (2009), "Breaking the symmetries of the book graph and the generalized Petersen graph", SIAM Journal on Discrete Mathematics , 23 (3): 1200–1216, doi:10.1137/080728640, MR 2538646 . Lal and Bhattacharjya (Theorem 4.3) credit this result to an unpublished masters thesis of K. S. Potanka (Virginia Polytechnic University, 1998).

[7] Cheng, Christine T. (2006), "On computing the distinguishing numbers of trees and forests", Electronic Journal of Combinatorics, 13 (1): R11, doi: 10.37236/1037 , MR 2200539 .

[8] Arvind, V.; Cheng, Christine T.; Devanur, Nikhil R. (2008), "On computing the distinguishing numbers of planar graphs and beyond: a counting approach", SIAM Journal on Discrete Mathematics , 22 (4): 1297–1324, arXiv: math/0703927 , doi:10.1137/07068686X, MR 2443115, S2CID 2402306 .

[c09-9] 1 2 Cheng, Christine T. (2009), "On computing the distinguishing and distinguishing chromatic numbers of interval graphs and other results", Discrete Mathematics , 309 (16): 5169–5182, doi: 10.1016/j.disc.2009.04.004 , MR 2548918 .

[10] Russell, Alexander; Sundaram, Ravi (1998), "A note on the asymptotics and computational complexity of graph distinguishability", Electronic Journal of Combinatorics , 5: R23, doi: 10.37236/1361 , MR 1617449 .

[11] Eschen, Elaine M.; Hoàng, Chính T.; Sritharan, R.; Stewart, Lorna (2011), "On the complexity of deciding whether the distinguishing chromatic number of a graph is at most two", Discrete Mathematics , 311 (6): 431–434, arXiv: 0907.0691 , doi:10.1016/j.disc.2010.12.013, MR 2799894, S2CID 7679211 .

[12] Collins, Karen L.; Trenk, Ann N. (2006), "The distinguishing chromatic number", Electronic Journal of Combinatorics , 13 (1): R16, doi: 10.37236/1042 , MR 2200544 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]