TY - JOUR

T1 - Uniquely d-colourable digraphs with large girth ii

T2 - Simplification via generalization

AU - Mark Kayll, P.

AU - Parsa, Esmaeil

N1 - Funding Information:
∗Partially supported by a grant from the Simons Foundation (#279367 to Mark Kayll). †Partially supported by a 2017 University of Montana Graduate Student Summer Research Award funded by the George and Dorothy Bryan Endowment and partially supported by a grant from the Simons Foundation (#279367 to Mark Kayll). This work forms part of the author’s PhD dissertation [17].
Publisher Copyright:
© The authors.

PY - 2021

Y1 - 2021

N2 - We prove that for every digraph D and every choice of positive integers k, ℓ there exists a digraph D∗ with girth at least ℓ together with a surjective acyclic homomorphism ψ: D∗ → D such that: (i) for every digraph C of order at most k, there exists an acyclic homomorphism D∗→ C if and only if there exists an acyclic homomorphism D → C; and (ii) for every D-pointed digraph C of order at most k and every acyclic homomorphism ϕ: D∗ → C there exists a unique acyclic homomorphism f: D → C such that ϕ = f ◦ ψ. This implies the main results in [A. Harutyunyan et al., Uniquely D-colourable digraphs with large girth, Canad. J. Math., 64(6) (2012), 1310–1328; MR2994666] analogously with how the work [J. Nešetřil and X. Zhu, On sparse graphs with given colorings and homomorphisms, J. Combin. Theory Ser. B, 90(1) (2004), 161–172; MR2041324] generalizes and extends [X. Zhu, Uniquely H-colorable graphs with large girth, J. Graph Theory, 23(1) (1996), 33–41; MR1402136].

AB - We prove that for every digraph D and every choice of positive integers k, ℓ there exists a digraph D∗ with girth at least ℓ together with a surjective acyclic homomorphism ψ: D∗ → D such that: (i) for every digraph C of order at most k, there exists an acyclic homomorphism D∗→ C if and only if there exists an acyclic homomorphism D → C; and (ii) for every D-pointed digraph C of order at most k and every acyclic homomorphism ϕ: D∗ → C there exists a unique acyclic homomorphism f: D → C such that ϕ = f ◦ ψ. This implies the main results in [A. Harutyunyan et al., Uniquely D-colourable digraphs with large girth, Canad. J. Math., 64(6) (2012), 1310–1328; MR2994666] analogously with how the work [J. Nešetřil and X. Zhu, On sparse graphs with given colorings and homomorphisms, J. Combin. Theory Ser. B, 90(1) (2004), 161–172; MR2041324] generalizes and extends [X. Zhu, Uniquely H-colorable graphs with large girth, J. Graph Theory, 23(1) (1996), 33–41; MR1402136].

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

U2 - 10.37236/9689

DO - 10.37236/9689

M3 - Article

AN - SCOPUS:85102198080

SN - 1077-8926

VL - 28

SP - 1

EP - 14

JO - Electronic Journal of Combinatorics

JF - Electronic Journal of Combinatorics

IS - 1

M1 - P1.48

ER -