Affiliations: Department of Algorithms and System Modeling, Gdańsk University of Technology, Poland. [email protected] | Faculty of Mathematics, Computer Science and Economics, University of Zielona Góra, Poland. [email protected]
Note: [] A preliminary version of this paper was presented at the International Workshop on Dynamic Networks: Algorithms and Security (DYNAS, Wrocław University of Technology, Poland, September 2009). Research partially supported by MNiSW grant N N516 196437. Address for correspondence: Department of Algorithms and System Modeling, Gdańsk University of Technology, Poland
Abstract: Dynamics is an inherent feature of many real life systems so it is natural to define and investigate the properties of models that reflect their dynamic nature. Dynamic graph colorings can be naturally applied in system modeling, e.g. for scheduling threads of parallel programs, time sharing in wireless networks, session scheduling in high-speed LAN's, channel assignment in WDM optical networks as well as traffic scheduling. In the dynamic setting of the problem, a graph we color is not given in advance and new vertices together with adjacent edges are revealed one after another at algorithm's input during the coloring process. Moreover, independently of the algorithm, some vertices may lose their colors and the algorithm may be asked to color them again. We formally define a dynamic graph coloring problem, the dynamic chromatic number and prove various bounds on its value. We also analyze the effectiveness of the dynamic coloring algorithm Dynamic-Fit for selected classes of graphs. In particular, we deal with trees, products of graphs and classes of graphs for which Dynamic-Fit is competitive. Motivated by applications, we state the problem of dynamic coloring with discoloring constraints for which the performance of the dynamic algorithm Time-Fit is analyzed and give a characterization of graphs k-critical for Time-Fit. Since for any fixed k > 0 the number of such graphs is finite, it is possible to decide in polynomial time whether Time-Fit will always color a given graph with at most k colors.
