Dynamic Coloring of Graphs

• Autorzy: Borowiecki P. , Sidorowicz E.
• Języki publikacji: EN

Abstrakty

EN

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 inWDM 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 problemof dynamic coloringwith discoloring constraints for which the performance of the dynamic algorithmTime-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.

Słowa kluczowe

EN

graph coloring; greedy coloring; Grundy number; critical graphs; algorithms; trees; graph product

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2012
• Tom: Vol. 114, nr 2
• Strony: 105--128
• Opis fizyczny: Bibliogr. 25 poz., wykr.

Twórcy

autor

Borowiecki P.

autor

Sidorowicz E.

• Department of Algorithms and System Modeling Gdańsk University of Technology, Poland,

Bibliografia

• [1] M. Asté, F. Havet and C. Linhares-Sales, Grundy number and products of graphs, Discrete Math. 310 (2010) 1482-1490.
• [2] A. Bar-Noy, A. Mayer, B. Schieber and M. Sudan, Guaranteeing fair service to persistent dependent tasks, SIAM J. Comput. 27 (1998) 1168-1189.
• [3] D.R. Bean, Effective coloration, J. Symbolic Logic 41 (1976) 469-480.
• [4] P. Borowiecki, On-line coloring of graphs, in: M. Kubale ed., Graph Colorings, Contemporary Mathematics 352, American Mathematical Society, 2004, 21-33.
• [5] P. Borowiecki, On-line P-coloring of graphs, Discuss. Math. Graph Theory 26 3 (2006) 389-401.
• [6] P. Borowiecki, On-line partitioning for on-line scheduling with resource conflicts, LNCS 4967 (2008) 981-990.
• [7] B. Brešar, P. Dorbec,W. Goddard, B.L. Hartnell,M.A. Henning, S. Klavžar and D.F. Rall, Vizing's conjecture: a survey and recent results, J. Graph Theory (online Feb. 2011) doi: 10.1002/jgt.20565.
• [8] C.A. Christen, S.M. Selkow, Some perfect coloring properties of graphs, J. Combin. Theory Ser. B 27 (1979) 49-59.
• [9] M. Drozdowski, Scheduling multiprocessor tasks - an overview, European J. Oper. Res. 94 (1996) 215-230.
• [10] B. Effantin, H. Kheddouci, Grundy number of graphs, Disscus. Math. Graph Theory 27 (2007) 5-18.
• [11] P. Erd˝os, R.C. Laskar, W.R. Hare and S.T. Hedetniemi, On the equality of the Grundy and ochromatic numbers of a graph, J. Graph Theory 11 (1987) 157-159.
• [12] A. Gyárfás, J. Lehel, On-line and First Fit coloring of graphs, J. Graph Theory 12 (1988) 217-227.
• [13] A. Gyárfás, J. Lehel, First-Fit and on-line chromatic number of families of graphs, Ars Combinatoria 29C (1990) 168-176.
• [14] A. Gyárfás, Z. Király and J. Lehel, On-line 3-chromatic graphs - II. Critical graphs, Discrete Math. 177 (1997) 99-122.
• [15] M.M. Halldórsson, Online Coloring Known Graphs, Electron. J. Comb. 7 (2000) 1-9.
• [16] R. Hammack, W. Imrich and S. Klavžar, Handbook of Graph Products, Discrete Mathematics and its Applications, CRC Press, 2011.
• [17] S.M. Hedetniemi, S.T. Hedetniemi and T. Beyer, A linear algorithm for the Grundy (coloring) number of a tree, Congr. Num. 36 (1982) 351-363.
• [18] S. Irani, V. Leung, Scheduling with conflicts on bipartite and interval graphs, J. Sched. 6 (2003) 287-307.
• [19] H.A. Kierstead, Coloring Graphs On-line, in: A. Fiat, G.J. Woeginger eds, Online algorithms - The State of the Art, LNCS 1442, Springer, Berlin, 1998, 281-305.
• [20] M. Kubale ed., Graph Colorings, ContemporaryMathematics 352, American Mathematical Society, 2004.
• [21] C.J.H. McDiarmid, Coloring random graphs badly, in: R.J. Wilson ed., Graph Theory and Combinatorics, Pitman, 1979, 76-86.
• [22] T.A. McKee, F.R. McMorris, Topics in intersection graph theory, SIAM Monographs on Discrete Mathematics and Applications, SIAM, Philadelphia, 1999.
• [23] S.D. Nikolopoulos, C. Papadopoulos, On the performance of the first-fit coloring algorithm on permutation graphs, Inform. Process. Lett. 75 (2000) 265-273.
• [24] M. Ślusarek, A lower bound for the First-Fit coloring of interval graphs, Zeszyty Naukowe Uniwersytetu Jagiellońskiego, Prace Informatyczne 5 (1993) 25-32.
• [25] J.A. Telle, A. Proskurowski, Algorithms for vertex partitioning problems on partial k-trees, SIAMJ. Discrete Math. 10 (1997) 529-550.