{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,6]],"date-time":"2026-02-06T01:17:09Z","timestamp":1770340629492,"version":"3.49.0"},"reference-count":71,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2017,11]]},"abstract":"<jats:p>Graph coloring is a fundamental graph problem that is widely applied in a variety of applications. The aim of graph coloring is to minimize the number of colors used to color the vertices in a graph such that no two incident vertices have the same color. Existing solutions for graph coloring mainly focus on computing a good coloring for a static graph. However, since many real-world graphs are highly dynamic, in this paper, we aim to incrementally maintain the graph coloring when the graph is dynamically updated. We target on two goals: high effectiveness and high efficiency. To achieve high effectiveness, we maintain the graph coloring in a way such that the coloring result is consistent with one of the best static graph coloring algorithms for large graphs. To achieve high efficiency, we investigate efficient incremental algorithms to update the graph coloring by exploring a small number of vertices. We design a color-propagation based algorithm which only explores the vertices within the 2-hop neighbors of the update-related and color-changed vertices. We then propose a novel color index to maintain some summary color information and, thus, bound the explored vertices within the neighbors of these vertices. Moreover, we derive some effective pruning rules to further reduce the number of propagated vertices. The experimental results demonstrate the high effectiveness and efficiency of our approach.<\/jats:p>","DOI":"10.14778\/3157794.3157802","type":"journal-article","created":{"date-parts":[[2017,12,12]],"date-time":"2017-12-12T18:33:38Z","timestamp":1513103618000},"page":"338-351","source":"Crossref","is-referenced-by-count":47,"title":["Effective and efficient dynamic graph coloring"],"prefix":"10.14778","volume":"11","author":[{"given":"Long","family":"Yuan","sequence":"first","affiliation":[{"name":"The University of New South Wales, Australia"}]},{"given":"Lu","family":"Qin","sequence":"additional","affiliation":[{"name":"University of Technology, Sydney, Australia"}]},{"given":"Xuemin","family":"Lin","sequence":"additional","affiliation":[{"name":"The University of New South Wales, Australia"}]},{"given":"Lijun","family":"Chang","sequence":"additional","affiliation":[{"name":"The University of Sydney, Australia"}]},{"given":"Wenjie","family":"Zhang","sequence":"additional","affiliation":[{"name":"The University of New South Wales, Australia"}]}],"member":"320","published-online":{"date-parts":[[2017,11]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544815"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/264216.264223"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2749450"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(02)00832-9"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-30165-5_30"},{"key":"e_1_2_1_6_1","volume-title":"Graph coloring for air traffic flow management. Annals of operations research, 130(1):163--178","author":"Barnier N.","year":"2004","unstructured":"N. Barnier and P. Brisset . Graph coloring for air traffic flow management. Annals of operations research, 130(1):163--178 , 2004 . N. Barnier and P. Brisset. Graph coloring for air traffic flow management. Annals of operations research, 130(1):163--178, 2004."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2006.05.014"},{"key":"e_1_2_1_8_1","first-page":"109","volume-title":"International Computing and Combinatorics Conference","author":"Foucaud F.","year":"2015","unstructured":"\u00c9. Bonnet, F. Foucaud , E. J. Kim , and F. Sikora . Complexity of grundy coloring and its variants . In International Computing and Combinatorics Conference , pages 109 -- 120 , 2015 . \u00c9. Bonnet, F. Foucaud, E. J. Kim, and F. Sikora. Complexity of grundy coloring and its variants. In International Computing and Combinatorics Conference, pages 109--120, 2015."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/2384787.2384788"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3056461"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/359094.359101"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-49192-8_19"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.04.025"},{"key":"e_1_2_1_14_1","first-page":"21","volume-title":"USENIX annual technical conference","author":"Carroll A.","year":"2010","unstructured":"A. Carroll , G. Heiser , An analysis of power consumption in a smartphone . In USENIX annual technical conference , pages 21 -- 21 , 2010 . A. Carroll, G. Heiser, et al. An analysis of power consumption in a smartphone. In USENIX annual technical conference, pages 21--21, 2010."},{"key":"e_1_2_1_15_1","first-page":"112","volume-title":"Proceedings of the Computational Symposium on Graph Coloring and its Generalizations","author":"Chiarandini M.","year":"2002","unstructured":"M. Chiarandini , T. St\u00fctzle , An application of iterated local search to graph coloring problem . In Proceedings of the Computational Symposium on Graph Coloring and its Generalizations , pages 112 -- 125 , 2002 . M. Chiarandini, T. St\u00fctzle, et al. An application of iterated local search to graph coloring problem. In Proceedings of the Computational Symposium on Graph Coloring and its Generalizations, pages 112--125, 2002."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(79)90067-4"},{"key":"e_1_2_1_17_1","volume-title":"Ants can colour graphs. Journal of the operational research society, 48(3):295--305","author":"Costa D.","year":"1997","unstructured":"D. Costa and A. Hertz . Ants can colour graphs. Journal of the operational research society, 48(3):295--305 , 1997 . D. Costa and A. Hertz. Ants can colour graphs. Journal of the operational research society, 48(3):295--305, 1997."},{"key":"e_1_2_1_18_1","volume-title":"Exploring the k-colorable landscape with iterated greedy. Cliques, coloring, and satisfiability: second DIMACS implementation challenge, 26:245--284","author":"Culberson J. C.","year":"1996","unstructured":"J. C. Culberson and F. Luo . Exploring the k-colorable landscape with iterated greedy. Cliques, coloring, and satisfiability: second DIMACS implementation challenge, 26:245--284 , 1996 . J. C. Culberson and F. Luo. Exploring the k-colorable landscape with iterated greedy. Cliques, coloring, and satisfiability: second DIMACS implementation challenge, 26:245--284, 1996."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/1882757.1882766"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/645824.668917"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.08.002"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2007.03.025"},{"key":"e_1_2_1_23_1","volume-title":"Workshop of COSSOM","author":"Dutot A.","year":"2007","unstructured":"A. Dutot , F. Guinand , D. Olivier , and Y. Pign\u00e9 . On the decentralized dynamic graph coloring problem . In Workshop of COSSOM , 2007 . A. Dutot, F. Guinand, D. Olivier, and Y. Pign\u00e9. On the decentralized dynamic graph coloring problem. In Workshop of COSSOM, 2007."},{"key":"e_1_2_1_24_1","first-page":"132","volume-title":"International Conference on the Practice and Theory of Automated Timetabling","author":"Erben W.","year":"2000","unstructured":"W. Erben . A grouping genetic algorithm for graph colouring and exam timetabling . In International Conference on the Practice and Theory of Automated Timetabling , pages 132 -- 156 , 2000 . W. Erben. A grouping genetic algorithm for graph colouring and exam timetabling. In International Conference on the Practice and Theory of Automated Timetabling, pages 132--156, 2000."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2610513"},{"key":"e_1_2_1_26_1","volume-title":"Hybrid evolutionary algorithms for graph coloring. Journal of combinatorial optimization, 3(4):379--397","author":"Galinier P.","year":"1999","unstructured":"P. Galinier and J.-K. Hao . Hybrid evolutionary algorithms for graph coloring. Journal of combinatorial optimization, 3(4):379--397 , 1999 . P. Galinier and J.-K. Hao. Hybrid evolutionary algorithms for graph coloring. Journal of combinatorial optimization, 3(4):379--397, 1999."},{"key":"e_1_2_1_27_1","volume-title":"Computers and Intractability","author":"Garey M. R.","year":"1990","unstructured":"M. R. Garey and D. S. Johnson . Computers and Intractability ; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co. , New York, NY, USA, 1990 . M. R. Garey and D. S. Johnson. Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York, NY, USA, 1990."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2513109.2513110"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190120212"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0836"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/139404.139452"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17493-3_17"},{"key":"e_1_2_1_33_1","volume-title":"Congr. Numer, 36: 351--363","author":"Hedetniemi S. M.","year":"1982","unstructured":"S. M. Hedetniemi , S. T. Hedetniemi , and T. Beyer . A linear algorithm for the grundy (coloring) number of a tree . Congr. Numer, 36: 351--363 , 1982 . S. M. Hedetniemi, S. T. Hedetniemi, and T. Beyer. A linear algorithm for the grundy (coloring) number of a tree. Congr. Numer, 36:351--363, 1982."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02239976"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2008.03.022"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2610495"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.39.3.378"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2015.05.015"},{"key":"e_1_2_1_39_1","volume-title":"Congressus Numerantium, 33(143--153)","author":"Kierstead H. A.","year":"1981","unstructured":"H. A. Kierstead and W. T. Trotter . An extremal problem in recursive combinatorics . Congressus Numerantium, 33(143--153) :98, 1981 . H. A. Kierstead and W. T. Trotter. An extremal problem in recursive combinatorics. Congressus Numerantium, 33(143--153):98, 1981."},{"key":"e_1_2_1_40_1","first-page":"211","volume-title":"The graph-colouring problem. Combinatorial optimization","author":"Korman S. M.","year":"1979","unstructured":"S. M. Korman . The graph-colouring problem. Combinatorial optimization , pages 211 -- 235 , 1979 . S. M. Korman. The graph-colouring problem. Combinatorial optimization, pages 211--235, 1979."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1011237503342"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2008.09.004"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2011.08.010"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(89)90096-4"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2009.07.016"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.1070.0245"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/1999995.2000020"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/2402.322385"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASONAM.2014.6921552"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1090\/dimacs\/026\/16"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.trb.2008.05.011"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1007\/11844297_89"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11083-008-9076-6"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783297"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(01)00290-6"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCCA.2011.6031437"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2016.7498232"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2010.01.015"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1571-0653(04)00007-1"},{"key":"e_1_2_1_60_1","first-page":"381","article-title":"Acodygra: an agent algorithm for coloring dynamic graphs","volume":"6","author":"Preuveneers D.","year":"2004","unstructured":"D. Preuveneers and Y. Berbers . Acodygra: an agent algorithm for coloring dynamic graphs . Symbolic and Numeric Algorithms for Scientific Computing , 6 : 381 -- 390 , 2004 . D. Preuveneers and Y. Berbers. Acodygra: an agent algorithm for coloring dynamic graphs. Symbolic and Numeric Algorithms for Scientific Computing, 6:381--390, 2004.","journal-title":"Symbolic and Numeric Algorithms for Scientific Computing"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1007\/s13278-014-0228-y"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1007\/11611257_9"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2008.08.006"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-015-9981-8"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480194275825"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1109\/FSCS.1990.89567"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/10.1.85"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2011.04.002"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2015.7113300"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2005.06.044"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132612"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3157794.3157802","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:37:51Z","timestamp":1672220271000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3157794.3157802"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,11]]},"references-count":71,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,11]]}},"alternative-id":["10.14778\/3157794.3157802"],"URL":"https:\/\/doi.org\/10.14778\/3157794.3157802","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2017,11]]}}}