oriented coloring

Oriented chromatic number of planar graphs ★★


An oriented colouring of an oriented graph is assignment $c$ of colours to the vertices such that no two arcs receive ordered pairs of colours $(c_1,c_2)$ and $(c_2,c_1)$. It is equivalent to a homomorphism of the digraph onto some tournament of order $k$.

\begin{problem} What is the maximal possible \Def[oriented chromatic number]{Oriented_coloring} of an oriented planar graph? \end{problem}

Keywords: oriented coloring; oriented graph; planar graph

Syndicate content