182:
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. 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.
170:
20:
69:, 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
82:
181:
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
345:. 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.
104:, 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
58:: 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
188:
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.
309:
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
157:
655:
Arvind, V.; Cheng, Christine T.; Devanur, Nikhil R. (2008), "On computing the distinguishing numbers of planar graphs and beyond: a counting approach",
604:. Lal and Bhattacharjya (Theorem 4.3) credit this result to an unpublished masters thesis of K. S. Potanka (Virginia Polytechnic University, 1998).
657:
579:
204:, only the Petersen graph itself and the graph of the cube have distinguishing number 3; the rest have distinguishing number 2.
713:
Cheng, Christine T. (2009), "On computing the distinguishing and distinguishing chromatic numbers of interval graphs and other results",
867:
758:
540:
376:
331:
231:
The exact complexity of computing distinguishing numbers is unclear, because it is closely related to the still-unknown complexity of
129:
has a significantly smaller distinguishing number, despite having the same symmetry group: it has a distinguishing coloring with
801:
715:
493:
243:, and testing whether it is at most two is "at least as hard as graph automorphism, but no harder than graph isomorphism".
293:, there exists a graph with that group as its group of automorphisms, with distinguishing number two. This result extends
577:
Lal, A. K.; Bhattacharjya, B. (2009), "Breaking the symmetries of the book graph and the generalized
Petersen graph",
236:
73:. With such a coloring, each key will be uniquely identified by its color and the sequence of colors surrounding it.
201:
799:(2011), "On the complexity of deciding whether the distinguishing chromatic number of a graph is at most two",
132:
909:
420:
429:
251:
A coloring of a given graph is distinguishing for that graph if and only if it is distinguishing for the
47:
434:
294:
213:
862:
836:
810:
692:
666:
615:
535:
455:
271:
51:
169:
753:
371:
232:
196:
has distinguishing number 3. However other than this graph and the complete graphs, all
876:
854:
820:
767:
724:
676:
627:
588:
549:
502:
439:
415:
385:
367:
252:
90:
19:
890:
832:
781:
738:
688:
641:
600:
563:
516:
464:
If a graph has no nontrivial automorphisms its distinguishing number is 1. In other words,
451:
399:
886:
828:
777:
734:
684:
637:
596:
559:
512:
447:
395:
225:
185:
24:
239:. Additionally, testing whether the distinguishing chromatic number is at most three is
283:
221:
193:
159:
colors, obtained by using a different ordered pair of colors for each pair of a vertex
101:
85:
Eight asymmetric graphs, each given a distinguishing coloring with only one color (red)
55:
43:
903:
796:
279:
173:
A distinguishing coloring of a ring of six keys, using two colors (red and unpainted)
754:"A note on the asymptotics and computational complexity of graph distinguishability"
840:
696:
531:
488:
459:
290:
217:
197:
94:
31:
178:
70:
824:
729:
507:
297:
that every finite group can be realized as the group of symmetries of a graph.
255:. Therefore, every graph has the same distinguishing number as its complement.
858:
267:
240:
81:
65:
Distinguishing colorings and distinguishing numbers were introduced by
680:
592:
443:
671:
16:
Assignment of colors to graph vertices that destroys all symmetries
881:
815:
772:
632:
390:
168:
80:
18:
554:
235:. However, it has been shown to belong to the complexity class
616:"On computing the distinguishing numbers of trees and forests"
89:
A graph has distinguishing number one if and only if it is
329:
Rubin, Frank (1979), "Problem 729: the blind man's keys",
200:
have distinguishing number 2. Similarly, among the
491:(2004), "The distinguishing number of the hypercube",
282:, the distinguishing number is two, and if it forms a
536:"Using determining sets to distinguish Kneser graphs"
418:(2006), "Distinguishing Cartesian powers of graphs",
135:
795:Eschen, Elaine M.; Hoàng, Chính T.; Sritharan, R.;
122:by attaching a degree-one vertex to each vertex of
97:has a distinguishing coloring with only one color.
151:
286:then the distinguishing number is at most three.
50:of the graph that destroys all of the nontrivial
342:
66:
341:. Solution in vol. 12, 1980. As cited by
8:
146:
136:
752:Russell, Alexander; Sundaram, Ravi (1998),
880:
814:
771:
728:
670:
631:
553:
506:
433:
389:
278:. If the automorphisms form a nontrivial
152:{\displaystyle \lceil {\sqrt {n}}\rceil }
139:
134:
321:
863:"The distinguishing chromatic number"
708:
706:
54:. The coloring does not need to be a
7:
658:SIAM Journal on Discrete Mathematics
580:SIAM Journal on Discrete Mathematics
361:
359:
357:
355:
353:
351:
868:Electronic Journal of Combinatorics
759:Electronic Journal of Combinatorics
620:Electronic Journal of Combinatorics
541:Electronic Journal of Combinatorics
377:Electronic Journal of Combinatorics
332:Journal of Recreational Mathematics
115:. However, the graph obtained from
14:
311:distinguishing chromatic number
266:is at most proportional to the
262:, the distinguishing number of
23:Distinguishing coloring of a 4-
343:Albertson & Collins (1996)
307:proper distinguishing coloring
212:The distinguishing numbers of
67:Albertson & Collins (1996)
1:
372:"Symmetry breaking in graphs"
614:Cheng, Christine T. (2006),
202:generalized Petersen graphs
166:and its attached neighbor.
926:
825:10.1016/j.disc.2010.12.013
730:10.1016/j.disc.2009.04.004
508:10.1016/j.disc.2003.11.018
208:Computational complexity
530:Albertson, Michael O.;
421:Journal of Graph Theory
366:Albertson, Michael O.;
52:symmetries of the graph
40:distinguishing labeling
36:distinguishing coloring
475:for asymmetric graphs.
174:
153:
86:
27:
247:Additional properties
172:
154:
84:
60:distinguishing number
22:
802:Discrete Mathematics
716:Discrete Mathematics
494:Discrete Mathematics
133:
93:. For instance, the
44:assignment of colors
224:can be computed in
414:Imrich, Wilfried;
175:
149:
87:
28:
855:Collins, Karen L.
723:(16): 5169–5182,
681:10.1137/07068686X
593:10.1137/080728640
444:10.1002/jgt.20190
368:Collins, Karen L.
270:of the number of
233:graph isomorphism
144:
46:or labels to the
42:of a graph is an
917:
895:
893:
884:
851:
845:
843:
818:
792:
786:
784:
775:
749:
743:
741:
732:
710:
701:
699:
674:
665:(4): 1297–1324,
652:
646:
644:
635:
611:
605:
603:
587:(3): 1200–1216,
574:
568:
566:
557:
532:Boutin, Debra L.
527:
521:
519:
510:
489:Cowen, Lenore J.
484:
478:
477:
474:
437:
410:
404:
402:
393:
363:
346:
340:
326:
295:Frucht's theorem
277:
265:
261:
258:For every graph
253:complement graph
186:Hypercube graphs
165:
158:
156:
155:
150:
145:
140:
128:
121:
114:
110:
925:
924:
920:
919:
918:
916:
915:
914:
900:
899:
898:
853:
852:
848:
794:
793:
789:
751:
750:
746:
712:
711:
704:
654:
653:
649:
613:
612:
608:
576:
575:
571:
529:
528:
524:
487:Bogstad, Bill;
486:
485:
481:
465:
413:
411:
407:
365:
364:
349:
328:
327:
323:
319:
303:
275:
263:
259:
249:
226:polynomial time
222:interval graphs
210:
164:
160:
131:
130:
127:
123:
120:
116:
112:
109:
105:
79:
56:proper coloring
25:hypercube graph
17:
12:
11:
5:
923:
921:
913:
912:
910:Graph coloring
902:
901:
897:
896:
846:
809:(6): 431–434,
797:Stewart, Lorna
787:
744:
702:
647:
606:
569:
522:
501:(1–3): 29–35,
479:
435:10.1.1.59.9242
428:(3): 250–260,
416:Klavžar, Sandi
405:
347:
320:
318:
315:
313:of the graph.
302:
299:
284:dihedral group
248:
245:
209:
206:
194:Petersen graph
162:
148:
143:
138:
125:
118:
107:
102:complete graph
78:
75:
62:of the graph.
15:
13:
10:
9:
6:
4:
3:
2:
922:
911:
908:
907:
905:
892:
888:
883:
882:10.37236/1042
878:
874:
870:
869:
864:
860:
859:Trenk, Ann N.
856:
850:
847:
842:
838:
834:
830:
826:
822:
817:
812:
808:
804:
803:
798:
791:
788:
783:
779:
774:
773:10.37236/1361
769:
765:
761:
760:
755:
748:
745:
740:
736:
731:
726:
722:
718:
717:
709:
707:
703:
698:
694:
690:
686:
682:
678:
673:
668:
664:
660:
659:
651:
648:
643:
639:
634:
633:10.37236/1037
629:
625:
621:
617:
610:
607:
602:
598:
594:
590:
586:
582:
581:
573:
570:
565:
561:
556:
551:
547:
543:
542:
537:
533:
526:
523:
518:
514:
509:
504:
500:
496:
495:
490:
483:
480:
476:
472:
468:
461:
457:
453:
449:
445:
441:
436:
431:
427:
423:
422:
417:
409:
406:
401:
397:
392:
391:10.37236/1242
387:
383:
379:
378:
373:
369:
362:
360:
358:
356:
354:
352:
348:
344:
338:
334:
333:
325:
322:
316:
314:
312:
308:
300:
298:
296:
292:
287:
285:
281:
280:abelian group
273:
272:automorphisms
269:
256:
254:
246:
244:
242:
238:
234:
229:
227:
223:
219:
218:planar graphs
215:
207:
205:
203:
199:
198:Kneser graphs
195:
190:
187:
183:
180:
171:
167:
141:
103:
98:
96:
92:
83:
76:
74:
72:
68:
63:
61:
57:
53:
49:
45:
41:
37:
33:
26:
21:
872:
866:
849:
806:
800:
790:
763:
757:
747:
720:
714:
672:math/0703927
662:
656:
650:
623:
619:
609:
584:
578:
572:
555:10.37236/938
545:
539:
525:
498:
492:
482:
470:
466:
463:
425:
419:
408:
381:
375:
336:
330:
324:
310:
306:
304:
291:finite group
288:
257:
250:
230:
211:
191:
184:
176:
99:
95:Frucht graph
88:
64:
59:
39:
35:
32:graph theory
29:
412:See, e.g.,
179:cycle graph
71:cycle graph
875:(1): R16,
626:(1): R11,
548:(1): R20,
384:(1): R18,
317:References
301:Variations
289:For every
91:asymmetric
816:0907.0691
430:CiteSeerX
268:logarithm
147:⌉
137:⌈
904:Category
861:(2006),
534:(2007),
370:(1996),
77:Examples
48:vertices
891:2200544
841:7679211
833:2799894
782:1617449
766:: R23,
739:2548918
697:2402306
689:2443115
642:2200539
601:2538646
564:2285824
517:2061481
460:6808067
452:2262268
400:1394549
241:NP-hard
889:
839:
831:
780:
737:
695:
687:
640:
599:
562:
515:
458:
450:
432:
398:
220:, and
177:For a
837:S2CID
811:arXiv
693:S2CID
667:arXiv
473:) = 1
456:S2CID
339:: 128
214:trees
100:In a
192:The
34:, a
877:doi
821:doi
807:311
768:doi
725:doi
721:309
677:doi
628:doi
589:doi
550:doi
503:doi
499:283
440:doi
386:doi
274:of
111:is
38:or
30:In
906::
887:MR
885:,
873:13
871:,
865:,
857:;
835:,
829:MR
827:,
819:,
805:,
778:MR
776:,
762:,
756:,
735:MR
733:,
719:,
705:^
691:,
685:MR
683:,
675:,
663:22
661:,
638:MR
636:,
624:13
622:,
618:,
597:MR
595:,
585:23
583:,
560:MR
558:,
546:14
544:,
538:,
513:MR
511:,
497:,
462:,
454:,
448:MR
446:,
438:,
426:53
424:,
396:MR
394:,
380:,
374:,
350:^
337:11
335:,
305:A
237:AM
228:.
216:,
894:.
879::
844:.
823::
813::
785:.
770::
764:5
742:.
727::
700:.
679::
669::
645:.
630::
591::
567:.
552::
520:.
505::
471:G
469:(
467:D
442::
403:.
388::
382:3
276:G
264:G
260:G
163:n
161:K
142:n
126:n
124:K
119:n
117:K
113:n
108:n
106:K
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
