More Web Proxy on the site http://driver.im/

article

Dynamic Coloring of Graphs

Authors:

Piotr Borowiecki,

Elżbieta SidorowiczAuthors Info & Claims

Fundamenta Informaticae, Volume 114, Issue 2

Pages 105 - 128

Published: 01 April 2012 Publication History

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.

References

[1]

M. Asté, F. Havet and C. Linhares-Sales, Grundy number and products of graphs, Discrete Math. 310 (2010) 1482-1490.

Digital Library

[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.

Digital Library

[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)

[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ös, 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.

Digital Library

[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.

Digital Library

[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, Contemporary Mathematics 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.

Digital Library

[24]

M. Slusarek, A lower bound for the First-Fit coloring of interval graphs, Zeszyty Naukowe Uniwersytetu Jagiellonskiego, Prace Informatyczne 5 (1993) 25-32.

[25]

J.A. Telle, A. Proskurowski, Algorithms for vertex partitioning problems on partial k-trees, SIAM J. Discrete Math. 10 (1997) 529-550.

Digital Library

Cited By

Barba LCardinal JKorman MLangerman SRenssen ARoeloffzen MVerdonschot S(2019)Dynamic Graph ColoringAlgorithmica10.1007/s00453-018-0473-y81:4(1319-1341)Online publication date: 1-Apr-2019
https://dl.acm.org/doi/10.1007/s00453-018-0473-y
Borowiecki P(2018)Computational aspects of greedy partitioning of graphsJournal of Combinatorial Optimization10.1007/s10878-017-0185-235:2(641-665)Online publication date: 1-Feb-2018
https://dl.acm.org/doi/10.1007/s10878-017-0185-2
Borowiecki PSidorowicz E(2018)Dynamic F-free Coloring of GraphsGraphs and Combinatorics10.1007/s00373-018-1886-834:3(457-475)Online publication date: 1-May-2018
https://dl.acm.org/doi/10.1007/s00373-018-1886-8
Show More Cited By

Dynamic Coloring of Graphs
1. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics
    2. Graph theory
2. Theory of computation

Recommendations

Dynamic Coloring of Graphs

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 ...
Minimum order of graphs with given coloring parameters

A complete k -coloring of a graph G = ( V , E ) is an assignment : V { 1 , , k } of colors to the vertices such that no two vertices of the same color are adjacent, and the union of any two color classes contains at least one edge. Three extensively ...
Dynamic F-free Coloring of Graphs

A problem of graph F-free coloring consists in partitioning the vertex set of a graph such that none of the resulting sets induces a graph containing a fixed graph F as an induced subgraph. In this paper we consider dynamic F-free coloring in which, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Fundamenta Informaticae

Fundamenta Informaticae Volume 114, Issue 2

April 2012

114 pages

ISSN:0169-2968

Issue’s Table of Contents

Publisher

IOS Press

Netherlands

Publication History

Published: 01 April 2012

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Barba LCardinal JKorman MLangerman SRenssen ARoeloffzen MVerdonschot S(2019)Dynamic Graph ColoringAlgorithmica10.1007/s00453-018-0473-y81:4(1319-1341)Online publication date: 1-Apr-2019
https://dl.acm.org/doi/10.1007/s00453-018-0473-y
Borowiecki P(2018)Computational aspects of greedy partitioning of graphsJournal of Combinatorial Optimization10.1007/s10878-017-0185-235:2(641-665)Online publication date: 1-Feb-2018
https://dl.acm.org/doi/10.1007/s10878-017-0185-2
Borowiecki PSidorowicz E(2018)Dynamic F-free Coloring of GraphsGraphs and Combinatorics10.1007/s00373-018-1886-834:3(457-475)Online publication date: 1-May-2018
https://dl.acm.org/doi/10.1007/s00373-018-1886-8
Yuan LQin LLin XChang LZhang W(2017)Effective and efficient dynamic graph coloringProceedings of the VLDB Endowment10.14778/3157794.315780211:3(338-351)Online publication date: 1-Nov-2017
https://dl.acm.org/doi/10.14778/3157794.3157802
Bacsó GBorowiecki PHujter MTuza Z(2015)Minimum order of graphs with given coloring parametersDiscrete Mathematics10.1016/j.disc.2014.12.002338:4(621-632)Online publication date: 6-Apr-2015
https://dl.acm.org/doi/10.1016/j.disc.2014.12.002
Borowiecki PRautenbach D(2015)New potential functions for greedy independence and coloringDiscrete Applied Mathematics10.1016/j.dam.2013.12.011182:C(61-72)Online publication date: 19-Feb-2015
https://dl.acm.org/doi/10.1016/j.dam.2013.12.011

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents