Radio coloring (original) (raw)
In graph theory, a branch of mathematics, a radio coloring of an undirected graph is a form of graph coloring in which one assigns positive integer labels to the graphssuch that the labels of adjacent vertices differ by at least two, and the labels of vertices at distance two from each other differ by at least one. Radio coloring was first studied by , under a different name, L(2,1)-labeling. It was called radio coloring by Frank Harary because it models the problem of channel assignment in radio broadcasting, while avoiding electromagnetic interference between radio stations that are near each other both in the graph and in their assigned channel frequencies.
| Property | Value |
|---|---|
| dbo:abstract | In graph theory, a branch of mathematics, a radio coloring of an undirected graph is a form of graph coloring in which one assigns positive integer labels to the graphssuch that the labels of adjacent vertices differ by at least two, and the labels of vertices at distance two from each other differ by at least one. Radio coloring was first studied by , under a different name, L(2,1)-labeling. It was called radio coloring by Frank Harary because it models the problem of channel assignment in radio broadcasting, while avoiding electromagnetic interference between radio stations that are near each other both in the graph and in their assigned channel frequencies. The span of a radio coloring is its maximum label, and the radio coloring number of a graph is the smallest possible span of a radio coloring. For instance, the graph consisting of two vertices with a single edge has radio coloring number 3: it has a radio coloring with one vertex labeled 1 and the other labeled 3, but it is not possible for a radio coloring of this graph to use only the labels 1 and 2. (en) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Radiocycle.png?width=300 |
| dbo:wikiPageID | 47160384 (xsd:integer) |
| dbo:wikiPageLength | 6067 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 977997860 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Electromagnetic_interference dbr:Undirected_graph dbc:Graph_coloring dbc:NP-complete_problems dbc:Extensions_and_generalizations_of_graphs dbr:Frank_Harary dbr:Graph_coloring dbr:NP-complete dbc:NP-hard_problems dbr:Complement_graph dbr:Tree_(graph_theory) dbr:Almost_all dbc:Radio_resource_management dbr:E_(complexity) dbr:Diameter_(graph_theory) dbr:Graph_theory dbr:Hamiltonian_path dbr:Bipartite_graph dbc:Computational_problems_in_graph_theory dbr:Cograph dbr:Planar_graph dbr:Split_graph dbr:Polynomial_time dbr:Integer dbr:Radio_broadcasting dbr:Channel_allocation_schemes dbr:File:Radiocycle.png |
| dbp:wikiPageUsesTemplate | dbt:Harvtxt dbt:Math dbt:Mvar dbt:Reflist |
| dcterms:subject | dbc:Graph_coloring dbc:NP-complete_problems dbc:Extensions_and_generalizations_of_graphs dbc:NP-hard_problems dbc:Radio_resource_management dbc:Computational_problems_in_graph_theory |
| gold:hypernym | dbr:Vertex |
| rdfs:comment | In graph theory, a branch of mathematics, a radio coloring of an undirected graph is a form of graph coloring in which one assigns positive integer labels to the graphssuch that the labels of adjacent vertices differ by at least two, and the labels of vertices at distance two from each other differ by at least one. Radio coloring was first studied by , under a different name, L(2,1)-labeling. It was called radio coloring by Frank Harary because it models the problem of channel assignment in radio broadcasting, while avoiding electromagnetic interference between radio stations that are near each other both in the graph and in their assigned channel frequencies. (en) |
| rdfs:label | Radio coloring (en) |
| owl:sameAs | yago-res:Radio coloring wikidata:Radio coloring https://global.dbpedia.org/id/xx1i |
| prov:wasDerivedFrom | wikipedia-en:Radio_coloring?oldid=977997860&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Radiocycle.png |
| foaf:isPrimaryTopicOf | wikipedia-en:Radio_coloring |
| is dbo:wikiPageWikiLink of | dbr:Cynthia_Wyels dbr:Incidence_coloring dbr:Interval_edge_coloring dbr:Graph_coloring |
| is foaf:primaryTopic of | wikipedia-en:Radio_coloring |
