Distinguishing coloring (original) (raw)
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.
| Property | Value |
|---|---|
| dbo:abstract | 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 , 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. (en) Характерная раскраска или характерная разметка графа — это назначение цветов или меток вершинам графа, которые разрушают нетривиальные симметрии графа. Не требуется, чтобы раскраска была правильной — смежным вершинам разрешено иметь одинаковый цвет. Для раскрашенного графа не должно существовать биективного отображения множества вершин с сохранением смежности и раскраски. Минимальное число цветов в характерной раскраске называется характерным числом графа. Характерные раскраски и характерные числа ввели Альбертсон и Коллинз, которые дали следующий пример для объяснения введения такой раскраски, основанный на головоломке, которую до этого сформулировал Франк Рубин: «Пусть у вас имеется связка ключей (на кольце) от различных дверей. Каждый ключ открывает только одну дверь, но все ключи выглядят одинаково (вы не можете их различить по внешнему виду). Сколько цветов вам нужно, чтобы раскрасить ключи и вы после этого могли полностью идентифицировать каждый ключ?» Этот пример решается с помощью характерной раскраски для графа-цикла. С помощью такой раскраски каждый ключ может быть однозначно идентифицирован по его цвету и цвету окружающих его ключей. (ru) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Distinguishing_4-hypercube.svg?width=300 |
| dbo:wikiPageID | 47480525 (xsd:integer) |
| dbo:wikiPageLength | 11362 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1110999409 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Hypercube_graph dbc:Graph_coloring dbr:Complete_graph dbr:Generalized_Petersen_graph dbr:Petersen_graph dbr:Graph_coloring dbr:NP-hard dbr:Logarithm dbr:Complement_graph dbr:Frucht's_theorem dbr:Frucht_graph dbr:Tree_(graph_theory) dbr:Cycle_graph dbr:Graph_automorphism dbr:Graph_isomorphism dbr:Graph_theory dbr:Asymmetric_graph dbr:Interval_graph dbr:Abelian_group dbr:Dihedral_group dbr:Arthur–Merlin_protocol dbr:Planar_graph dbr:Polynomial_time dbr:Kneser_graph dbr:Vertex_(graph_theory) dbr:Finite_group dbr:File:Asym-graph.PNG dbr:File:6-key_distinguishing_coloring.jpg dbr:File:Distinguishing_4-hypercube.svg |
| dbp:wikiPageUsesTemplate | dbt:Harvtxt dbt:Mvar dbt:Reflist dbt:Short_description |
| dcterms:subject | dbc:Graph_coloring |
| rdfs:comment | 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. (en) Характерная раскраска или характерная разметка графа — это назначение цветов или меток вершинам графа, которые разрушают нетривиальные симметрии графа. Не требуется, чтобы раскраска была правильной — смежным вершинам разрешено иметь одинаковый цвет. Для раскрашенного графа не должно существовать биективного отображения множества вершин с сохранением смежности и раскраски. Минимальное число цветов в характерной раскраске называется характерным числом графа. (ru) |
| rdfs:label | Distinguishing coloring (en) Характерная раскраска (ru) |
| owl:sameAs | wikidata:Distinguishing coloring dbpedia-ru:Distinguishing coloring https://global.dbpedia.org/id/2NfN7 |
| prov:wasDerivedFrom | wikipedia-en:Distinguishing_coloring?oldid=1110999409&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Asym-graph.png wiki-commons:Special:FilePath/6-key_distinguishing_coloring.jpg wiki-commons:Special:FilePath/Distinguishing_4-hypercube.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Distinguishing_coloring |
| is dbo:wikiPageRedirects of | dbr:Distinguishing_number |
| is dbo:wikiPageWikiLink of | dbr:Melody_Chan dbr:Ann_Trenk dbr:Graph_coloring dbr:Distinguishing_number dbr:Graph_automorphism |
| is foaf:primaryTopic of | wikipedia-en:Distinguishing_coloring |
