TY - JOUR
T1 - Uniquely d-colourable digraphs with large girth ii
T2 - Simplification via generalization
AU - Mark Kayll, P.
AU - Parsa, Esmaeil
N1 - 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 -