Uniquely d-colourable digraphs with large girth ii: Simplification via generalization

P. Mark Kayll, Esmaeil Parsa

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

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 languageEnglish
Article numberP1.48
Pages (from-to)1-14
Number of pages14
JournalElectronic Journal of Combinatorics
Volume28
Issue number1
DOIs
StatePublished - 2021

Fingerprint

Dive into the research topics of 'Uniquely d-colourable digraphs with large girth ii: Simplification via generalization'. Together they form a unique fingerprint.

Cite this