Home » Keyword index

oriented graph


Graph Theory » Coloring » Vertex coloring

Oriented chromatic number of planar graphs ★★

Author(s):

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 $.

Problem   What is the maximal possible oriented chromatic number of an oriented planar graph?

Keywords: oriented coloring; oriented graph; planar graph

Posted by Robert Samal
updated August 4th, 2007
add new comment
Syndicate content