A connection between circular colorings and periodic schedules

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


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 over(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 u v with weight cu v represents a data channel with communication cost, and tokens on arc u v represent the input data of task vertex v. Dynamically, if vertex u operates at time t, then u removes one token from each of its in-arc; if u v is an out-arc of u, then at time t + cu v vertex u places one token on arc u v. Computer scientists are interested in designing, for each vertex u, a sequence of time instants {fu (1), fu (2), fu (3), ...} such that vertex u starts its kth operation at time fu (k) and each in-arc of u contains at least one token at that time. The set of functions {fu : u ∈ V (over(G, →))} is called a schedule of over(G, →). Computer scientists are particularly interested in periodic schedules. Given a timed marked graph over(G, →), they ask if there exist a period p > 0 and real numbers xu such that over(G, →) has a periodic schedule of the form fu (k) = xu + p (k - 1) for each vertex u and any positive integer k. 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.

Original languageEnglish
Pages (from-to)1663-1668
Number of pages6
JournalDiscrete Applied Mathematics
Issue number7
StatePublished - 6 Apr 2009


  • Circular chromatic number
  • Edge-weighted graph
  • Minty's theorem
  • Periodic scheduling
  • Timed marked graph


Dive into the research topics of 'A connection between circular colorings and periodic schedules'. Together they form a unique fingerprint.

Cite this