The oriented chromatic number o(H) of an oriented graph H is defined to be the minimum order of an oriented graph H′ such that H has a homomorphism to H′. If each graph in a class script K sign has a homomorphism to the same H′, then H′ is script K sign-universal. Let script P signk denote the class of orientations of planar graphs with girth at least k. Clearly, script P sign3 ⊃ script P sign4 ⊃ script P sign5. . . We discuss the existence of script P signk-universal graphs with special properties. It is known (see Raspaud and Sopena, 1994) that there exists a script P sign3-universal graph on 80 vertices. We prove here that (1) there exist no planar script P sign4-universal graphs; (2) there exists a planar script P sign16-universal graph on 6 vertices; (3) for any k, there exist no planar script P signk-universal graphs of girth at least 6; (4) for any k, there exists a script P sign40k-universal graph of girth at least k + 1.
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics