Abstract
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].
| Original language | English |
|---|---|
| Article number | P1.48 |
| Pages (from-to) | 1-14 |
| Number of pages | 14 |
| Journal | Electronic Journal of Combinatorics |
| Volume | 28 |
| Issue number | 1 |
| DOIs | |
| State | Published - 2021 |
Funding
∗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].
| Funders | Funder number |
|---|---|
| Simons Foundation | 279367 |