Homomorphism bounds for oriented planar graphs
T. H. Marshall · Journal of Graph Theory · 2007
Abstract If ${\cal C}$ is a class of oriented graphs (directed graphs without opposite arcs), then an oriented graph is a homomorphism bound for ${\cal C}$ if there is a homomorphism from each graph in ${\cal C}$ 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