Homomorphism bounds for oriented planar graphs

If is a class of oriented graphs (directed graphs without opposite arcs), then an oriented graph is a homomorphism bound for if there is a homomorphism from each graph in to H. We find some necessary conditions for a graph to be a homomorphism bound for the class of oriented planar graphs and prove that such a graph must have maximum degree at least 16; thus there exists an oriented planar graph with oriented chromatic number at least 17. © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 175–190, 2007