### Abstract

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 sign_{k} denote the class of orientations of planar graphs with girth at least k. Clearly, script P sign_{3} ⊃ script P sign_{4} ⊃ script P sign_{5}. . . We discuss the existence of script P sign_{k}-universal graphs with special properties. It is known (see Raspaud and Sopena, 1994) that there exists a script P sign_{3}-universal graph on 80 vertices. We prove here that (1) there exist no planar script P sign_{4}-universal graphs; (2) there exists a planar script P sign_{16}-universal graph on 6 vertices; (3) for any k, there exist no planar script P sign_{k}-universal graphs of girth at least 6; (4) for any k, there exists a script P sign_{40k}-universal graph of girth at least k + 1.

Original language | English (US) |
---|---|

Pages (from-to) | 73-85 |

Number of pages | 13 |

Journal | Discrete Mathematics |

Volume | 188 |

Issue number | 1-3 |

DOIs | |

State | Published - Jun 28 1998 |

Externally published | Yes |

### ASJC Scopus subject areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics

## Fingerprint Dive into the research topics of 'On universal graphs for planar oriented graphs of a given girth'. Together they form a unique fingerprint.

## Cite this

*Discrete Mathematics*,

*188*(1-3), 73-85. https://doi.org/10.1016/S0012-365X(97)00276-8