{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,4]],"date-time":"2026-07-04T02:38:39Z","timestamp":1783132719017,"version":"3.54.6"},"reference-count":17,"publisher":"Springer Science and Business Media LLC","issue":"9","license":[{"start":{"date-parts":[[2020,2,21]],"date-time":"2020-02-21T00:00:00Z","timestamp":1582243200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,2,21]],"date-time":"2020-02-21T00:00:00Z","timestamp":1582243200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,9]]},"DOI":"10.1007\/s00453-020-00689-4","type":"journal-article","created":{"date-parts":[[2020,2,21]],"date-time":"2020-02-21T06:02:59Z","timestamp":1582264979000},"page":"2395-2414","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["A New Vertex Coloring Heuristic and Corresponding Chromatic Number"],"prefix":"10.1007","volume":"82","author":[{"given":"Manouchehr","family":"Zaker","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2020,2,21]]},"reference":[{"key":"689_CR1","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/0020-0190(92)90209-E","volume":"44","author":"A Bar-Noy","year":"1992","unstructured":"Bar-Noy, A., Motwani, R., Naor, J.: The Greedy algorithm is optimal for on-line edge coloring. Inform. Process. Lett. 44, 251\u2013253 (1992)","journal-title":"Inform. Process. Lett."},{"key":"689_CR2","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/j.dam.2017.12.022","volume":"243","author":"E Bonnet","year":"2018","unstructured":"Bonnet, E., Foucaud, F., Kim, E.J., Sikora, F.: Complexity of Grundy coloring and its variants. Discret. Appl. Math. 243, 99\u2013114 (2018)","journal-title":"Discret. Appl. Math."},{"key":"689_CR3","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1145\/359094.359101","volume":"22","author":"D Brelaz","year":"1979","unstructured":"Brelaz, D.: New methods to color the vertices of a graph. Commun. ACM 22, 251\u2013256 (1979)","journal-title":"Commun. ACM"},{"key":"689_CR4","volume-title":"Iterated Greedy Graph Coloring and the Difficulty Landscape","author":"JC Culberson","year":"1992","unstructured":"Culberson, J.C.: Iterated Greedy Graph Coloring and the Difficulty Landscape. Department of Computer Science, University of Western Ontario, London (1992)"},{"key":"689_CR5","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1090\/dimacs\/026\/13","volume":"26","author":"JC Culberson","year":"1996","unstructured":"Culberson, J.C., Luo, F.: Exploring the $$k$$-colorable landscape with iterated Greedy. Cliques, Color., Satisf.: Second DIMACS Implement. Chall. 26, 245\u2013284 (1996)","journal-title":"Cliques, Color., Satisf.: Second DIMACS Implement. Chall."},{"key":"689_CR6","volume-title":"Parametrized Algorithms","author":"M Cygan","year":"2016","unstructured":"Cygan, M., et al.: Parametrized Algorithms. Springer, Berlin (2016)"},{"key":"689_CR7","doi-asserted-by":"publisher","first-page":"2157","DOI":"10.1016\/j.disc.2016.03.011","volume":"339","author":"B Effantin","year":"2016","unstructured":"Effantin, B., Gastineau, N., Togni, O.: A characterization of $$b$$-chromatic and partial Grundy numbers by induced subgraphs. Discret. Math. 339, 2157\u20132167 (2016)","journal-title":"Discret. Math."},{"key":"689_CR8","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1002\/jgt.3190120212","volume":"12","author":"A Gy\u00e1rf\u00e1s","year":"1988","unstructured":"Gy\u00e1rf\u00e1s, A., Lehel, J.: On-line and first-fit coloring of graphs. J. Graph Theory 12, 217\u2013227 (1988)","journal-title":"J. Graph Theory"},{"key":"689_CR9","doi-asserted-by":"publisher","first-page":"885","DOI":"10.1007\/s00453-011-9604-4","volume":"65","author":"F Havet","year":"2013","unstructured":"Havet, F., Sampaio, L.: On the Grundy and $$b$$-chromatic numbers of a graph. Algorithmica 65, 885\u2013899 (2013)","journal-title":"Algorithmica"},{"key":"689_CR10","first-page":"351","volume":"36","author":"SM Hedetniemi","year":"1982","unstructured":"Hedetniemi, S.M., Hedetniemi, S., Beyer, T.: A linear algorithm for the Grundy (coloring) number of a tree. Congr. Numer. 36, 351\u2013363 (1982)","journal-title":"Congr. Numer."},{"key":"689_CR11","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/S0166-218X(98)00146-2","volume":"91","author":"RW Irving","year":"1999","unstructured":"Irving, R.W., Manlove, D.F.: The b-chromatic number of a graph. Discret. Appl. Math. 91, 127\u2013141 (1999)","journal-title":"Discret. Appl. Math."},{"key":"689_CR12","doi-asserted-by":"publisher","first-page":"184","DOI":"10.1016\/j.dam.2017.08.008","volume":"235","author":"M Jakovac","year":"2018","unstructured":"Jakovac, M., Peterin, I.: The $$b$$-chromatic number and related topics\u2014a survey. Discret. Appl. Math. 235, 184\u2013201 (2018)","journal-title":"Discret. Appl. Math."},{"key":"689_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1111\/j.1475-3995.2009.00696.x","volume":"17","author":"E Malaguti","year":"2010","unstructured":"Malaguti, E., Toth, P.: A survey on vertex coloring problems. Int. Trans. Oper. Res. 17, 1\u201334 (2010)","journal-title":"Int. Trans. Oper. Res."},{"key":"689_CR14","doi-asserted-by":"publisher","first-page":"906","DOI":"10.1137\/0218062","volume":"18","author":"RM Verma","year":"1989","unstructured":"Verma, R.M., Reyner, S.W.: An analysis of a good algorithm for the subtree problem, corrected. SIAM J. Comput. 18, 906\u2013908 (1989)","journal-title":"SIAM J. Comput."},{"key":"689_CR15","first-page":"325","volume":"31","author":"M Zaker","year":"2005","unstructured":"Zaker, M.: Grundy chromatic number of the complement of bipartite graphs. Australas. J. Comb. 31, 325\u2013330 (2005)","journal-title":"Australas. J. Comb."},{"key":"689_CR16","doi-asserted-by":"publisher","first-page":"3166","DOI":"10.1016\/j.disc.2005.06.044","volume":"306","author":"M Zaker","year":"2006","unstructured":"Zaker, M.: Results on the Grundy chromatic number of graphs. Discret. Math. 306, 3166\u20133173 (2006)","journal-title":"Discret. Math."},{"key":"689_CR17","doi-asserted-by":"publisher","first-page":"103","DOI":"10.4086\/toc.2007.v003a006","volume":"3","author":"D Zuckerman","year":"2007","unstructured":"Zuckerman, D.: Linear degree extractors and the inaproximablity of max clique and chromatic number. Theor. Comput. 3, 103\u2013128 (2007)","journal-title":"Theor. Comput."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00689-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-020-00689-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00689-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,20]],"date-time":"2021-02-20T01:22:15Z","timestamp":1613784135000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-020-00689-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,2,21]]},"references-count":17,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2020,9]]}},"alternative-id":["689"],"URL":"https:\/\/doi.org\/10.1007\/s00453-020-00689-4","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,2,21]]},"assertion":[{"value":"5 September 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 February 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 February 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}