{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T04:35:37Z","timestamp":1743136537525,"version":"3.40.3"},"publisher-location":"Cham","reference-count":26,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319213972"},{"type":"electronic","value":"9783319213989"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-21398-9_9","type":"book-chapter","created":{"date-parts":[[2015,6,23]],"date-time":"2015-06-23T15:12:41Z","timestamp":1435072361000},"page":"109-120","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Complexity of Grundy Coloring and Its Variants"],"prefix":"10.1007","author":[{"given":"\u00c9douard","family":"Bonnet","sequence":"first","affiliation":[]},{"given":"Florent","family":"Foucaud","sequence":"additional","affiliation":[]},{"given":"Eun Jung","family":"Kim","sequence":"additional","affiliation":[]},{"given":"Florian","family":"Sikora","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,6,24]]},"reference":[{"issue":"4","key":"9_CR1","doi-asserted-by":"publisher","first-page":"844","DOI":"10.1145\/210332.210337","volume":"42","author":"N Alon","year":"1995","unstructured":"Alon, N., Yuster, R., Zwick, U.: Color-coding. Journal of the ACM 42(4), 844\u2013856 (1995)","journal-title":"Journal of the ACM"},{"issue":"18","key":"9_CR2","doi-asserted-by":"publisher","first-page":"2514","DOI":"10.1016\/j.dam.2011.08.016","volume":"160","author":"J Araujo","year":"2012","unstructured":"Araujo, J., Sales, C.L.: On the Grundy number of graphs with few P$$_{\\text{4 }}$$\u2019s. Discrete Applied Mathematics 160(18), 2514\u20132522 (2012)","journal-title":"Discrete Applied Mathematics"},{"key":"9_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1007\/978-3-642-54423-1_38","volume-title":"LATIN 2014: Theoretical Informatics","author":"F Benevides","year":"2014","unstructured":"Benevides, F., Campos, V., Dourado, M., Griffiths, S., Morris, R., Sampaio, L., Silva, A.: Connected greedy colourings. In: Pardo, A., Viola, A. (eds.) LATIN 2014. LNCS, vol. 8392, pp. 433\u2013441. Springer, Heidelberg (2014)"},{"key":"9_CR4","doi-asserted-by":"crossref","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: Fourier meets M\u00f6bius: fast subset convolution. In: Proc. 39th Annual ACM Symposium on Theory of Computing, STOC 2007, pp. 67\u201374. ACM (2007)","DOI":"10.1145\/1250790.1250801"},{"issue":"1\u20132","key":"9_CR5","first-page":"1","volume":"11","author":"HL Bodlaender","year":"1993","unstructured":"Bodlaender, H.L.: A tourist guide through treewidth. Acta Cybernetica 11(1\u20132), 1\u201321 (1993)","journal-title":"Acta Cybernetica"},{"key":"9_CR6","doi-asserted-by":"crossref","unstructured":"Bonnet, E., Foucaud, F., Kim, E.J., Sikora, F.: Complexity of grundy coloring and its variants (2014). CoRR, abs\/1407.5336","DOI":"10.1007\/978-3-319-21398-9_9"},{"issue":"12\u201313","key":"9_CR7","doi-asserted-by":"publisher","first-page":"2088","DOI":"10.1016\/j.disc.2012.03.029","volume":"312","author":"GJ Chang","year":"2012","unstructured":"Chang, G.J., Hsu, H.-C.: First-fit chromatic numbers of $$d$$-degenerate graphs. Discrete Mathematics 312(12\u201313), 2088\u20132090 (2012)","journal-title":"Discrete Mathematics"},{"issue":"1","key":"9_CR8","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/0095-8956(79)90067-4","volume":"27","author":"CA Christen","year":"1979","unstructured":"Christen, C.A., Selkow, S.M.: Some perfect coloring properties of graphs. Journal of Combinatorial Theory, Series B 27(1), 49\u201359 (1979)","journal-title":"Journal of Combinatorial Theory, Series B"},{"issue":"1","key":"9_CR9","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1137\/S0097539799360768","volume":"31","author":"J Flum","year":"2001","unstructured":"Flum, J., Grohe, M.: Fixed-parameter tractability, definability, and model-checking. SIAM Journal on Computing 31(1), 113\u2013145 (2001)","journal-title":"SIAM Journal on Computing"},{"key":"9_CR10","unstructured":"Goyal, N., Vishwanathan, S.: NP-completeness of undirected Grundy numbering and related problems. Manuscript (1997)"},{"key":"9_CR11","first-page":"6","volume":"2","author":"PM Grundy","year":"1939","unstructured":"Grundy, P.M.: Mathematics and games. Eureka 2, 6\u20138 (1939)","journal-title":"Eureka"},{"issue":"2","key":"9_CR12","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 colorings of graphs. Journal of Graph Theory 12(2), 217\u2013227 (1988)","journal-title":"Journal of Graph Theory"},{"key":"9_CR13","unstructured":"Havet, F., Maia, A.K., Yu, M.-L.: Complexity of greedy edge-colouring. Research report RR-8171, INRIA, December 2012"},{"issue":"4","key":"9_CR14","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(4), 885\u2013899 (2013)","journal-title":"Algorithmica"},{"key":"9_CR15","first-page":"351","volume":"36","author":"SM Hedetniemi","year":"1982","unstructured":"Hedetniemi, S.M., Hedetniemi, S.T., Beyer, T.: A linear algorithm for the Grundy (coloring) number of a tree. Congressus Numerantium 36, 351\u2013363 (1982)","journal-title":"Congressus Numerantium"},{"issue":"4","key":"9_CR16","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? Journal of Computer and System Sciences 63(4), 512\u2013530 (2001)","journal-title":"Journal of Computer and System Sciences"},{"issue":"7","key":"9_CR17","doi-asserted-by":"publisher","first-page":"605","DOI":"10.1016\/j.dam.2010.05.002","volume":"159","author":"HA Kierstead","year":"2011","unstructured":"Kierstead, H.A., Saoub, K.R.: First-fit coloring of bounded tolerance graphs. Discrete Applied Mathematics 159(7), 605\u2013611 (2011)","journal-title":"Discrete Applied Mathematics"},{"key":"9_CR18","doi-asserted-by":"crossref","unstructured":"Kortsarz, G.: A lower bound for approximating Grundy numbering. Discrete Mathematics & Theoretical Computer Science 9(1) (2007)","DOI":"10.46298\/dmtcs.391"},{"key":"9_CR19","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Marx, D., Saurabh, S.: Known algorithms on graphs of bounded treewidth are probably optimal. In: Proc. 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, pp. 777\u2013789. SIAM (2011)","DOI":"10.1137\/1.9781611973082.61"},{"issue":"1","key":"9_CR20","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1007\/BF02760024","volume":"3","author":"J Moon","year":"1965","unstructured":"Moon, J., Moser, L.: On cliques in graphs. Israel Journal of Mathematics 3(1), 23\u201328 (1965)","journal-title":"Israel Journal of Mathematics"},{"issue":"1","key":"9_CR21","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/s11083-008-9076-6","volume":"25","author":"NS Narayanaswamy","year":"2008","unstructured":"Narayanaswamy, N.S., Babu, R.S.: A note on first-fit coloring of interval graphs. Order 25(1), 49\u201353 (2008)","journal-title":"Order"},{"key":"9_CR22","unstructured":"Papadimitriou, C.H.: Computational complexity. Addison-Wesley (1994)"},{"key":"9_CR23","unstructured":"Sampaio, L.: Algorithmic aspects of graph colouring heuristics. PhD thesis, University of Nice-Sophia Antipolis, November 2012"},{"issue":"4","key":"9_CR24","doi-asserted-by":"publisher","first-page":"529","DOI":"10.1137\/S0895480194275825","volume":"10","author":"JA Telle","year":"1997","unstructured":"Telle, J.A., Proskurowski, A.: Algorithms for vertex partitioning problems on partial k-trees. SIAM Journal on Discrete Mathematics 10(4), 529\u2013550 (1997)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"9_CR25","first-page":"325","volume":"31","author":"M Zaker","year":"2005","unstructured":"Zaker, M.: The Grundy chromatic number of the complement of bipartite graphs. Australasian Journal of Combinatorics 31, 325\u2013329 (2005)","journal-title":"Australasian Journal of Combinatorics"},{"issue":"23","key":"9_CR26","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. Discrete Mathematics 306(23), 3166\u20133173 (2006)","journal-title":"Discrete Mathematics"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-21398-9_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,20]],"date-time":"2023-01-20T15:32:24Z","timestamp":1674228744000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-21398-9_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319213972","9783319213989"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-21398-9_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"24 June 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}