A short construction of highly chromatic digraphs without short cycles


  • Michael Severino University of Montana




digraph, chromatic number, acyclic homomorphism, girth


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\H{o}s [Graph theory and probability, Canad. J. Math. {\bf11} (1959), 34--38], it was shown probabilistically in [D. Bokal et al., The circular chromatic number of a digraph, J. Graph Theory {\bf46} (2004), no. 3, 227--240] that there exist digraphs with arbitrarily large girth and chromatic number. Here we give a construction of such digraphs.



[1] J. Bang-Jensen and G. Gutin. Digraphs: Theory, Algorithms and Applications. Springer Mono- graphs in Mathematics. Springer-Verlag London Ltd., London, 2001.

[2] D. Bokal, G. Fijavˇz, M. Juvan, P. M. Kayll, and B. Mohar. The circular chromatic number of a digraph. J. Graph Theory, 46(3):227–240, 2004.

[3] P. Erd ̋os. Graph theory and probability. Canad. J. Math., 11:34–38, 1959.

[4] I. Kˇr ́ıˇz. A hypergraph-free construction of highly chromatic graphs without short cycles. Com-

binatorica, 9(2):227–229, 1989.

[5] L. Lov ́asz. On chromatic number of finite set-systems. Acta Math. Acad. Sci. Hungar., 19:59–

67, 1968.

[6] J. Neˇsetˇril and V. R ̈odl. A short proof of the existence of highly chromatic hypergraphs without

short cycles. J. Combin. Theory Ser. B, 27(2):225–227, 1979.