TY - JOUR

T1 - ON COLOURING ORIENTED GRAPHS OF LARGE GIRTH

AU - Kayll, P. Mark

AU - Morris, Michael

N1 - Publisher Copyright:
© 2023 University of Calgary. All rights reserved.

PY - 2023

Y1 - 2023

N2 - 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.

AB - 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.

KW - girth

KW - homomorphisms

KW - oriented chromatic number

KW - oriented graph

UR - http://www.scopus.com/inward/record.url?scp=85185157850&partnerID=8YFLogxK

U2 - 10.55016/ojs/cdm.v18i2.73457

DO - 10.55016/ojs/cdm.v18i2.73457

M3 - Article

AN - SCOPUS:85185157850

VL - 18

SP - 234

EP - 243

JO - Contributions to Discrete Mathematics

JF - Contributions to Discrete Mathematics

IS - 2

ER -