A connection between circular colorings and periodic schedules

We show that there is a curious connection between circular colorings of edge-weighted digraphs and periodic schedules of timed marked graphs. Circular coloring of an edge-weighted digraph was introduced by Mohar [B. Mohar, Circular colorings of edge-weighted graphs, J. Graph Theory 43 (2003) 107–116]. This kind of coloring is a very natural generalization of several well-known graph coloring problems including the usual circular coloring [X. Zhu, Circular chromatic number: A survey, Discrete Math. 229 (2001) 371–410] and the circular coloring of vertex-weighted graphs [W. Deuber, X. Zhu, Circular coloring of weighted graphs, J. Graph Theory 23 (1996) 365–376]. Timed marked graphs G→ [R.M. Karp, R.E. Miller, Properties of a model for parallel computations: Determinancy, termination, queuing, SIAM J. Appl. Math. 14 (1966) 1390–1411] are used, in computer science, to model the data movement in parallel computations, where a vertex represents a task, an arc uvuv with weight cuvcuv represents a data channel with communication cost, and tokens on arc uvuv represent the input data of task vertex vv. Dynamically, if vertex uu operates at time tt, then uu removes one token from each of its in-arc; if uvuv is an out-arc of uu, then at time t+cuvt+cuv vertex uu places one token on arc uvuv. Computer scientists are interested in designing, for each vertex uu, a sequence of time instants {fu(1),fu(2),fu(3),…}{fu(1),fu(2),fu(3),…} such that vertex uu starts its kkth operation at time fu(k)fu(k) and each in-arc of uu contains at least one token at that time. The set of functions {fu:u∈V(G→)} is called a schedule of G→. Computer scientists are particularly interested in periodic schedules. Given a timed marked graph G→, they ask if there exist a period p>0p>0 and real numbers xuxu such that G→ has a periodic schedule of the form fu(k)=xu+p(k−1)fu(k)=xu+p(k−1) for each vertex uu and any positive integer kk. In this note we demonstrate an unexpected connection between circular colorings and periodic schedules. The aim of this note is to provide a possibility of translating problems and methods from one area of graph coloring to another area of computer science.