Uniquely D-colourable digraphs with large girth. II: Simplification via generalization

DOI10.37236/9689zbMATH Open1459.05081arXiv2007.01981OpenAlexW3138790773MaRDI QIDQ2656903FDOQ2656903

Authors: P. Mark Kayll, Esmaeil Parsa 

Publication date: 17 March 2021

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: We prove that for every digraph $D$ and every choice of positive integers $k$, $ell$ there exists a digraph $D^{*}$ with girth at least $ell$ together with a surjective acyclic homomorphism $psicolon{D}^{\ast }oD$ such that: (i) for every digraph $C$ of order at most $k$, there exists an acyclic homomorphism $D^{\ast }oC$ if and only if there exists an acyclic homomorphism $DoC$; and (ii) for every $D$-pointed digraph $C$ of order at most $k$ and every acyclic homomorphism $varphicolon{D}^{\ast }oC$ there exists a unique acyclic homomorphism $fcolonDoC$ such that $varphi=fcircpsi$. 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. Nev{s}etv{r}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].

Full work available at URL: https://arxiv.org/abs/2007.01981

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Uniquely \(D\)-colourable digraphs with large girth
• A construction of uniquely \(n\)-colorable digraphs with arbitrarily large digirth
• A note on coloring digraphs of large girth
• scientific article; zbMATH DE number 927067
• Two results on the digraph chromatic number

zbMATH Keywords

\(D\)-colouringuniquely circularly \(r\)-colourable digraphs

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Graph theory
• Title not available (Why is that?)
• Title not available (Why is that?)
• Graph Theory and Probability
• Title not available (Why is that?)
• The circular chromatic number of a digraph
• Digraphs
• The probabilistic method
• Graph colouring and the probabilistic method
• Coloring, sparseness and girth
• On chromatic number of finite set-systems
• A hypergraph-free construction of highly chromatic graphs without short cycles
• Uniquely Colourable Graphs with Large Girth
• On colorings of graphs without short cycles
• On sparse graphs with given colorings and homomorphisms.
• Uniquely \(D\)-colourable digraphs with large girth
• A construction of uniquely \(n\)-colorable digraphs with arbitrarily large digirth
• A short construction of highly chromatic digraphs without short cycles

Cited In (6)

• Uniquely colorable graphs up to automorphisms
• Homomorphisms to digraphs with large girth and oriented colorings of minimal series-parallel digraphs
• Uniquely \(D\)-colourable digraphs with large girth
• Title not available (Why is that?)
• On colouring oriented graphs of large girth
• A construction of uniquely \(n\)-colorable digraphs with arbitrarily large digirth

This page was built for publication: Uniquely \(D\)-colourable digraphs with large girth. II: Simplification via generalization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2656903)