×

Homomorphisms to powers of digraphs. (English) Zbl 0994.05071

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.

MSC:

05C20 Directed graphs (digraphs), tournaments
05C75 Structural characterization of families of graphs
05C15 Coloring of graphs and hypergraphs
05C38 Paths and cycles
PDFBibTeX XMLCite
Full Text: DOI