Oriented coloring

Oriented coloring

In graph theory, oriented graph coloring is a special type of graph coloring. Namely, it is an assignment of "colors" to vertices of an oriented graph that

  • is proper: no two adjacent vertices get the same color, and
  • respects the orientation: if (xy) and (uv) are arcs of the graph then it is not possible that colors of x and v and of y and u are the same.

An oriented chromatic number of a graph G is the least number of colors needed in an oriented coloring; it is usually denoted by \scriptstyle\chi_o(G).

Properties

We need an oriented graph, otherwise no oriented coloring exists. If the graph has loops (directed 2-cycles), the first (second, respectively) condition will be violated.

An oriented graph coloring corresponds to graph homomorphism into a tournament.

Examples

The oriented chromatic number of a directed 5-cycle is 5.


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Look at other dictionaries:

  • Graph coloring — A proper vertex coloring of the Petersen graph with 3 colors, the minimum number possible. In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called colors to elements of a graph… …   Wikipedia

  • Edge coloring — A 3 edge coloring of the Desargues graph. In graph theory, an edge coloring of a graph is an assignment of “colors” to the edges of the graph so that no two adjacent edges have the same color. For example, the figure to the right shows an edge… …   Wikipedia

  • Circular coloring — In graph theory, circular coloring may be viewed as a refinement of usual graph coloring. The circular chromatic number of a graph G, denoted χc(G) can be given by any of the following definitions, all of which are equivalent (for finite graphs) …   Wikipedia

  • Fox n-coloring — In the mathematical field of knot theory, Fox n coloring is a method of specifying a representation of a knot group (or a link group) onto the dihedral group of order n where n is an odd integer by coloring arcs in a link diagram (the… …   Wikipedia

  • List of mathematics articles (O) — NOTOC O O minimal theory O Nan group O(n) Obelus Oberwolfach Prize Object of the mind Object theory Oblate spheroid Oblate spheroidal coordinates Oblique projection Oblique reflection Observability Observability Gramian Observable subgroup… …   Wikipedia

  • Ida Van Smith — an African American pilot and flight instructor was born in 1917 in Lumberton, North Carolina. Early life Smith is the youngest of three children and grew up in a loving and sheltered environment. Her mother was African American and her father… …   Wikipedia

  • OptimJ — Paradigm(s) object oriented Appeared in 2006 (2006) Designed by Ateji Influenced by Java Website …   Wikipedia

  • Degeneracy (graph theory) — In graph theory, a k degenerate graph is an undirected graph in which every subgraph has a vertex of degree at most k: that is, some vertex in the subgraph touches k or fewer of the subgraph s edges. The degeneracy of a graph is the smallest… …   Wikipedia

  • MAPS OF EREẒ ISRAEL — Graphic descriptions of Ereẓ Israel relating to its topography and history and based on factual data, are not only extremely valuable sources for the reconstruction of the physiographic and anthropogenic conditions prevailing there at the time… …   Encyclopedia of Judaism

  • List of terms relating to algorithms and data structures — The [http://www.nist.gov/dads/ NIST Dictionary of Algorithms and Data Structures] is a reference work maintained by the U.S. National Institute of Standards and Technology. It defines a large number of terms relating to algorithms and data… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”