ON COLOURING ORIENTED GRAPHS OF LARGE GIRTH

P. Mark Kayll, Michael Morris

Research output: Contribution to journalArticlepeer-review

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 languageEnglish
Pages (from-to)234-243
Number of pages10
JournalContributions to Discrete Mathematics
Volume18
Issue number2
DOIs
StatePublished - 2023

Keywords

  • girth
  • homomorphisms
  • oriented chromatic number
  • oriented graph

Fingerprint

Dive into the research topics of 'ON COLOURING ORIENTED GRAPHS OF LARGE GIRTH'. Together they form a unique fingerprint.

Cite this