## Abstract

We prove that for every oriented graph D and every choice of positive integers k and ℓ, there exists an oriented graph D^{∗} along with a surjective homomorphism ψ: V (D^{∗}) → V (D) such that: (i) girth(D^{∗}) ≥ ℓ; (ii) for every oriented graph C with at most k vertices, there exists a homomorphism from D^{∗} to C if and only if there exists a homomorphism from D to C; and (iii) for every D-pointed oriented graph C with at most k vertices and for every homomorphism φ: V (D^{∗}) → V (C) there exists a unique homomorphism f : V (D) → V (C) such that φ = f ◦ ψ. Determining the oriented chromatic number of an oriented graph D is equivalent to finding the smallest integer k such that D admits a homomorphism to an order-k tournament, so our main theorem yields results on the girth and oriented chromatic number of oriented graphs. While our main proof is probabilistic (hence nonconstructive), for any given ℓ ≥ 3 and k ≥ 5, we include a construction of an oriented graph with girth ℓ and oriented chromatic number k.

Original language | English |
---|---|

Pages (from-to) | 234-243 |

Number of pages | 10 |

Journal | Contributions to Discrete Mathematics |

Volume | 18 |

Issue number | 2 |

DOIs | |

State | Published - 2023 |

### Funding

Received by the editors September 2, 2021, and in revised form June 13, 2023. 2020 Mathematics Subject Classification. Primary 05C15, 05C20; Secondary 05C60, 60C05. Key words and phrases. oriented graph, oriented chromatic number, girth, homomorphisms. PMK was partially supported by a grant from the Simons Foundation (#279367 to Mark Kayll). This work forms part of Michael Morris’ MA thesis.

Funders | Funder number |
---|---|

Simons Foundation | 279367 |

## Keywords

- girth
- homomorphisms
- oriented chromatic number
- oriented graph