Brewster, Richard C.; Hell, Pavol Homomorphisms to powers of digraphs. (English) Zbl 0994.05071 Discrete Math. 244, No. 1-3, 31-41 (2002). Summary: Given a digraph \(G\) and a sufficiently long directed path \(P\), a folklore result says that \(G\) is homomorphic to \(P\) if and only if all cycles in \(G\) are balanced (the same number of forward and backward arcs). The purpose of this paper is to study homomorphisms of digraphs \(G\) that contain unbalanced cycles. In this case, we may be able to find a homomorphism of \(G\) to a power of \(P\). Our main result states that the minimum power of \(P\) to which \(G\) admits a homomorphism equals the maximum imbalance (ratio of forward and backward arcs) of any cycle in \(G\). The proof also yields a polynomial time algorithm to find this minimum power of \(P\). We identity a larger class of digraphs \(H\) for which the minimum power problem can be solved in polynomial time, it includes all oriented paths \(H\). By relating our powers of paths to complete graphs and so-called circular graphs, we are able to deduce a classical result of Minty regarding the chromatic number, as well as its more recent extension, by Goddyn, Tarsi, and Zhang, to the circular chromatic number. Cited in 3 Documents MSC: 05C20 Directed graphs (digraphs), tournaments 05C75 Structural characterization of families of graphs 05C15 Coloring of graphs and hypergraphs 05C38 Paths and cycles Keywords:min-max theorem; characterizations; homomorphisms of digraphs; polynomial time algorithm; minimum power problem; circular chromatic number PDFBibTeX XMLCite \textit{R. C. Brewster} and \textit{P. Hell}, Discrete Math. 244, No. 1--3, 31--41 (2002; Zbl 0994.05071) Full Text: DOI