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 (x, y) and (u, v) 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 . 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.