Coloring Digraphs with Forbidden Cycles

Original · EN

Let k and r be two integers with k ≥ 2 and k≥ r ≥ 1. In this paper we show that (1) if a strongly connected digraph D contains no directed cycle of length 1 modulo k, then D is k-colorable; and (2) if a digraph D contains no directed cycle of length r modulo k, then D can be vertex-colored with k colors so that each color class induces an acyclic subdigraph in D. The first result gives an affirmative answer to a question posed by Tuza in 1992, and the second implies the following strong form of a conjecture of Diwan, Kenkre and Vishwanathan: If an undirected graph G contains no cycle of length r modulo k, then G is k-colorable if r≠ 2 and (k+1)-colorable otherwise. Our results also strengthen several classical theorems on graph coloring proved by Bondy, Erdős and Hajnal, Gallai and Roy, Gyárfás, etc.