Matches in DBpedia 2015-10 for { <http://dbpedia.org/resource/Distinguishing_coloring> ?p ?o }
Showing triples 1 to 49 of
49
with 100 triples per page.
- Distinguishing_coloring 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 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?" 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.".
- Distinguishing_coloring thumbnail Distinguishing_4-hypercube.svg?width=300.
- Distinguishing_coloring wikiPageID "47480525".
- Distinguishing_coloring wikiPageLength "10983".
- Distinguishing_coloring wikiPageOutDegree "32".
- Distinguishing_coloring wikiPageRevisionID "676915802".
- Distinguishing_coloring wikiPageWikiLink Abelian_group.
- Distinguishing_coloring wikiPageWikiLink Arthur–Merlin_protocol.
- Distinguishing_coloring wikiPageWikiLink Asymmetric_graph.
- Distinguishing_coloring wikiPageWikiLink Category:Graph_coloring.
- Distinguishing_coloring wikiPageWikiLink Complement_graph.
- Distinguishing_coloring wikiPageWikiLink Complete_graph.
- Distinguishing_coloring wikiPageWikiLink Cycle_graph.
- Distinguishing_coloring wikiPageWikiLink Dihedral_group.
- Distinguishing_coloring wikiPageWikiLink Finite_group.
- Distinguishing_coloring wikiPageWikiLink Frucht_graph.
- Distinguishing_coloring wikiPageWikiLink Fruchts_theorem.
- Distinguishing_coloring wikiPageWikiLink Generalized_Petersen_graph.
- Distinguishing_coloring wikiPageWikiLink Graph_automorphism.
- Distinguishing_coloring wikiPageWikiLink Graph_coloring.
- Distinguishing_coloring wikiPageWikiLink Graph_isomorphism.
- Distinguishing_coloring wikiPageWikiLink Graph_theory.
- Distinguishing_coloring wikiPageWikiLink Hypercube_graph.
- Distinguishing_coloring wikiPageWikiLink Interval_graph.
- Distinguishing_coloring wikiPageWikiLink Kneser_graph.
- Distinguishing_coloring wikiPageWikiLink Logarithm.
- Distinguishing_coloring wikiPageWikiLink NP-hard.
- Distinguishing_coloring wikiPageWikiLink NP-hardness.
- Distinguishing_coloring wikiPageWikiLink Petersen_graph.
- Distinguishing_coloring wikiPageWikiLink Planar_graph.
- Distinguishing_coloring wikiPageWikiLink Polynomial_time.
- Distinguishing_coloring wikiPageWikiLink Time_complexity.
- Distinguishing_coloring wikiPageWikiLink Tree_(graph_theory).
- Distinguishing_coloring wikiPageWikiLink Vertex_(graph_theory).
- Distinguishing_coloring wikiPageWikiLink File:6-key_distinguishing_coloring.jpg.
- Distinguishing_coloring wikiPageWikiLink File:Asym-graph.PNG.
- Distinguishing_coloring wikiPageWikiLink File:Distinguishing_4-hypercube.svg.
- Distinguishing_coloring wikiPageWikiLinkText "Distinguishing coloring".
- Distinguishing_coloring hasPhotoCollection Distinguishing_coloring.
- Distinguishing_coloring wikiPageUsesTemplate Template:Harvtxt.
- Distinguishing_coloring wikiPageUsesTemplate Template:Mvar.
- Distinguishing_coloring wikiPageUsesTemplate Template:Reflist.
- Distinguishing_coloring subject Category:Graph_coloring.
- Distinguishing_coloring hypernym Assignment.
- Distinguishing_coloring 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.".
- Distinguishing_coloring label "Distinguishing coloring".
- Distinguishing_coloring wasDerivedFrom Distinguishing_coloring?oldid=676915802.
- Distinguishing_coloring depiction Distinguishing_4-hypercube.svg.
- Distinguishing_coloring isPrimaryTopicOf Distinguishing_coloring.
