In graph theory, oriented graph coloring is a special type of graph coloring. Namely, it isan assignment of colors to vertices of an oriented graph that
* is proper: no two adjacent vertices get the same color, and
* is consistently oriented: if vertices and have the same color, and vertices and have the same color, then and cannot both be edges in the graph. Equivalently, an oriented graph coloring of a graph G is an oriented graph H (whose vertices represent colors and whose arcs represent valid orientations between colors) such that there exists a homomorphism from G to H.
Attributes | Values |
---|
rdfs:label
| - Oriented coloring (en)
- Ориентированная раскраска графа (ru)
|
rdfs:comment
| - Ориентированная раскраска графа — это специальный вид раскраски графов. А именно, это назначение цветов вершинам ориентированного графа, которое
* правильное — никакие две смежные вершины не получают один и тот же цвет,
* сохраняется ориентация — если (x, y) и (u, v) являются дугами в графе, то недопустимо, чтобы цвета вершин x и v, а также цвета вершин y и u совпадали. Другое определение: Ориентированная k-раскраска орграфа H есть ориентированный гомоморфизм в k-вершинный орграф H*. (ru)
- In graph theory, oriented graph coloring is a special type of graph coloring. Namely, it isan assignment of colors to vertices of an oriented graph that
* is proper: no two adjacent vertices get the same color, and
* is consistently oriented: if vertices and have the same color, and vertices and have the same color, then and cannot both be edges in the graph. Equivalently, an oriented graph coloring of a graph G is an oriented graph H (whose vertices represent colors and whose arcs represent valid orientations between colors) such that there exists a homomorphism from G to H. (en)
|
dcterms:subject
| |
Wikipage page ID
| |
Wikipage revision ID
| |
Link from a Wikipage to another Wikipage
| |
Link from a Wikipage to an external page
| |
sameAs
| |
dbp:wikiPageUsesTemplate
| |
has abstract
| - In graph theory, oriented graph coloring is a special type of graph coloring. Namely, it isan assignment of colors to vertices of an oriented graph that
* is proper: no two adjacent vertices get the same color, and
* is consistently oriented: if vertices and have the same color, and vertices and have the same color, then and cannot both be edges in the graph. Equivalently, an oriented graph coloring of a graph G is an oriented graph H (whose vertices represent colors and whose arcs represent valid orientations between colors) such that there exists a homomorphism from G to H. An oriented chromatic number of a graph G is the fewest colors needed in an oriented coloring;it is usually denoted by . The same definition can be extended to undirected graphs, as well, by defining the oriented chromatic number of an undirected graph to be the largest oriented chromatic number of any of its orientations. (en)
- Ориентированная раскраска графа — это специальный вид раскраски графов. А именно, это назначение цветов вершинам ориентированного графа, которое
* правильное — никакие две смежные вершины не получают один и тот же цвет,
* сохраняется ориентация — если (x, y) и (u, v) являются дугами в графе, то недопустимо, чтобы цвета вершин x и v, а также цвета вершин y и u совпадали. Другое определение: Ориентированная k-раскраска орграфа H есть ориентированный гомоморфизм в k-вершинный орграф H*. (ru)
|
prov:wasDerivedFrom
| |
page length (characters) of wiki page
| |
foaf:isPrimaryTopicOf
| |
is Link from a Wikipage to another Wikipage
of | |
is foaf:primaryTopic
of | |