Home » Subject » Graph Theory » Coloring » Vertex coloring
Importance: Medium ✭✭
Author(s):
Subject: Graph Theory
» Coloring
» » Vertex coloring
Keywords: oriented coloring
oriented graph
planar graph
Recomm. for undergrads: no
Posted by: Robert Samal
on: August 4th, 2007

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?

Raspaud and Sopena [RS] showed using Borodin's result about acyclic chromatic number of planar graphs, that every planar oriented graph has oriented chromatic number at most 80. (Their motivation came from a work of Courcelle [C] concerning the monadic second-order logic of graphs. That, however, deals with a stronger variant of coloring.)

On the other hand, Marshall [M] showed that there is an oriented planar graph with oriented chromatic number at least~17.

Bibliography

[C] B. Courcelle, The monadic second order logic of graphs VI: On several representations of graphs by relational structures, Discrete Appl. Math. 54 ( 1994),

[M] T. H. Marshall. On $ \cal P $-universal graphs. Research Report 2001-510, KAM-DIMATIA Series, 2001.

*[RS] A. Raspaud and E. Sopena. Good and semi-strong colorings of oriented planar graphs. Inform. Process. Lett., 51(4):171–174, 1994. MathSciNet


* indicates original appearance(s) of problem.
add new comment

Reply

Comments are limited to a maximum of 1000 characters.
More information about formatting options