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

DOI10.37236/9689MaRDI QIDQ2656903zbMATH OpenOpenAlexFDO

Authors P. Mark Kayll, Esmaeil Parsa

Publication date 17 March 2021

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

Copyright license Creative Commons Attribution 4.0 International

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

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

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Abstract: We prove that for every digraph $D$ and every choice of positive integers $k$, $ell$ there exists a digraph $D^{\ast }$ 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].

Review text

Summary: We prove that for every digraph \(D\) and every choice of positive integers \(k, \ell\) there exists a digraph \(D^\ast\) with girth at least \(\ell\) together with a surjective acyclic homomorphism \(\psi\colon D^\ast\to D\) such that: (i) for every digraph \(C\) of order at most \(k\), there exists an acyclic homomorphism \(D^\ast\to C\) if and only if there exists an acyclic homomorphism \(D\to C\); and (ii) for every \(D\)-pointed digraph \(C\) of order at most \(k\) and every acyclic homomorphism \(\varphi\colon D^\ast\to C\) there exists a unique acyclic homomorphism \(f\colon D\to C\) such that \(\varphi=f\circ\psi \). This implies the main results in [\textit{A. Harutyunyan} et al., Can. J. Math. 64, No. 6, 1310--1328 (2012; Zbl 1254.05057)] analogously with how the work [\textit{J. Nešetřil} and \textit{X. Zhu}, J. Comb. Theory, Ser. B 90, No. 1, 161--172 (2004; Zbl 1033.05044)] generalizes and extends [\textit{X. Zhu}, J. Graph Theory 23, No. 1, 33--41 (1996; Zbl 0864.05037)].

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

Cites work

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

Cited in

(6)

• Homomorphisms to digraphs with large girth and oriented colorings of minimal series-parallel digraphs
• Uniquely D-colourable digraphs with large girth
• scientific article; zbMATH DE number 927067 (Why is no real title available?)
• A construction of uniquely \(n\)-colorable digraphs with arbitrarily large digirth
• Uniquely colorable graphs up to automorphisms
• On colouring oriented graphs of large girth

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)