Digraphs and homomorphisms: Cores, colorings, and constructions
Michael Severino · The Mathematics Enthusiast · 2014
A natural digraph analogue of the graph-theoretic concept of an ‘independent set’ is that of an acyclic set, namely a set of vertices not spanning a directed cycle. Hence a digraph analogue of a graph coloring is a decomposition of the vertex set into acyclic sets. In the spirit of a famous theorem of P. Erdős [Graph theory and probability, Canad. J. Math. 11:34–38, (1959)], it was shown probabilistically in [D. Bokal et al., The circular chromatic number of a digraph, J. Graph Theory 46(3): 227–240, (2004)] that there exist digraphs with arbitrarily large digirth and chromatic number. Here we give a construction of such digraphs and define a new product of these highly chromatic digraphs with the directed analogue of the complete graph. This product gives a construction of uniquely n-colorable digraphs without short cycles. The graph-theoretic notion of ‘homomorphism’ also gives rise to a digraph analogue. An acyclic homomorphism from a digraph D to a digraph H is a mapping 𝜑 : V (D) → V (H) such that uv ∈ A (D) implies that either 𝜑(u)𝜑(v) ∈ A(H) or 𝜑(u) = 𝜑(v), and all the 'fibers' 𝜑-1(v), for v ∈ V(H), of 𝜑 are acyclic. In this language, a core is a digraph D for which there does not exist an acyclic homomorphism from D to itself. Here we prove some basic results about digraph cores and construct new classes of cores. We also define a digraph-theoretic analogue to the graph-theoretic ‘fractional chromatic number’ and prove results relating it to other well-known digraph invariants. We see that it behaves similarly to the graph-theoretic analogue.