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 image [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 image with weight image represents a data channel with communication cost, and tokens on arc image represent the input data of task vertex image. Dynamically, if vertex image operates at time image, then image removes one token from each of its in-arc; if image is an out-arc of image, then at time image vertex image places one token on arc image. Computer scientists are interested in designing, for each vertex image, a sequence of time instants image such that vertex image starts its imageth operation at time image and each in-arc of image contains at least one token at that time. The set of functions image is called a schedule of image. Computer scientists are particularly interested in periodic schedules. Given a timed marked graph image, they ask if there exist a period image and real numbers image such that image has a periodic schedule of the form image for each vertex image and any positive integer image. 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.