{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,22]],"date-time":"2025-05-22T02:30:34Z","timestamp":1747881034117,"version":"3.40.5"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,7,16]],"date-time":"2022-07-16T00:00:00Z","timestamp":1657929600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,7,16]],"date-time":"2022-07-16T00:00:00Z","timestamp":1657929600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"name":"ANR","award":["ANR-17-CE23-0010"],"award-info":[{"award-number":["ANR-17-CE23-0010"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2023,1]]},"DOI":"10.1007\/s00453-022-01001-2","type":"journal-article","created":{"date-parts":[[2022,7,16]],"date-time":"2022-07-16T06:02:40Z","timestamp":1657951360000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Grundy Coloring and Friends, Half-Graphs, Bicliques"],"prefix":"10.1007","volume":"85","author":[{"given":"Pierre","family":"Aboulker","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1653-5822","authenticated-orcid":false,"given":"\u00c9douard","family":"Bonnet","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6824-0516","authenticated-orcid":false,"given":"Eun Jung","family":"Kim","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2670-6258","authenticated-orcid":false,"given":"Florian","family":"Sikora","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,7,16]]},"reference":[{"issue":"3","key":"1001_CR1","doi-asserted-by":"publisher","first-page":"304","DOI":"10.1002\/jgt.22252","volume":"89","author":"P Aboulker","year":"2018","unstructured":"Aboulker, P., Bang-Jensen, J., Bousquet, N., Charbit, P., Havet, F., Maffray, F., Zamora, J.: $$\\chi $$-bounded families of oriented graphs. J. Graph Theory 89(3), 304\u2013326 (2018). https:\/\/doi.org\/10.1002\/jgt.22252","journal-title":"J. Graph Theory"},{"issue":"4","key":"1001_CR2","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. J. ACM 42(4), 844\u2013856 (1995)","journal-title":"J. ACM"},{"doi-asserted-by":"publisher","unstructured":"Bonnet, \u00c9., Bousquet, N., Charbit, P., Thomass\u00e9, S., Watrigant, R.: Parameterized complexity of independent set in h-free graphs. In: 13th International Symposium on Parameterized and Exact Computation, IPEC 2018, August 20\u201324, 2018, Helsinki, Finland, pp. 17:1\u201317:13 (2018). https:\/\/doi.org\/10.4230\/LIPIcs.IPEC.2018.17","key":"1001_CR3","DOI":"10.4230\/LIPIcs.IPEC.2018.17"},{"key":"1001_CR4","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/j.dam.2017.12.022","volume":"243","author":"\u00c9 Bonnet","year":"2018","unstructured":"Bonnet, \u00c9., Foucaud, F., Kim, E.J., Sikora, F.: Complexity of Gundy coloring and its variants. Discrete Appl. Math. 243, 99\u2013114 (2018). https:\/\/doi.org\/10.1016\/j.dam.2017.12.022","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"1001_CR5","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1093\/comjnl\/bxm086","volume":"51","author":"L Cai","year":"2008","unstructured":"Cai, L.: Parameterized complexity of cardinality constrained optimization problems. Comput. J. 51(1), 102\u2013121 (2008). https:\/\/doi.org\/10.1093\/comjnl\/bxm086","journal-title":"Comput. J."},{"doi-asserted-by":"publisher","unstructured":"Cai, L., Chan, S.M., Chan, S.O.: Random separation: a new method for solving fixed-cardinality optimization problems. In: Parameterized and Exact Computation, Second International workshop, IWPEC 2006, Z\u00fcrich, Switzerland, September 13\u201315, 2006, Proceedings, pp. 239\u2013250 (2006). https:\/\/doi.org\/10.1007\/11847250_22","key":"1001_CR6","DOI":"10.1007\/11847250_22"},{"issue":"4","key":"1001_CR7","doi-asserted-by":"publisher","first-page":"654","DOI":"10.1016\/S0022-0000(03)00073-4","volume":"67","author":"M Cesati","year":"2003","unstructured":"Cesati, M.: The Turing way to parameterized complexity. J. Comput. Syst. Sci. 67(4), 654\u2013685 (2003). https:\/\/doi.org\/10.1016\/S0022-0000(03)00073-4","journal-title":"J. Comput. Syst. Sci."},{"issue":"8","key":"1001_CR8","doi-asserted-by":"publisher","first-page":"1346","DOI":"10.1016\/j.jcss.2006.04.007","volume":"72","author":"J Chen","year":"2006","unstructured":"Chen, J., Huang, X., Kanj, I.A., Xia, G.: Strong computational lower bounds via parameterized complexity. J. Comput. Syst. Sci. 72(8), 1346\u20131367 (2006). https:\/\/doi.org\/10.1016\/j.jcss.2006.04.007","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"1001_CR9","doi-asserted-by":"publisher","first-page":"1171","DOI":"10.1137\/15M1032077","volume":"45","author":"R Chitnis","year":"2016","unstructured":"Chitnis, R., Cygan, M., Hajiaghayi, M.T., Pilipczuk, M., Pilipczuk, M.: Designing FPT algorithms for cut problems using randomized contractions. SIAM J. Comput. 45(4), 1171\u20131229 (2016). https:\/\/doi.org\/10.1137\/15M1032077","journal-title":"SIAM J. Comput."},{"issue":"1","key":"1001_CR10","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. J. Comb. Theory Ser. B 27(1), 49\u201359 (1979)","journal-title":"J. Comb. Theory Ser. B"},{"key":"1001_CR11","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Berlin (2015). https:\/\/doi.org\/10.1007\/978-3-319-21275-3"},{"key":"1001_CR12","volume-title":"Graph Theory, Volume 173 of Graduate Texts in Mathematics","author":"R Diestel","year":"2012","unstructured":"Diestel, R.: Graph Theory, Volume 173 of Graduate Texts in Mathematics, 4th edn. Springer, Berlin (2012)","edition":"4"},{"key":"1001_CR13","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized Complexity","author":"RG Downey","year":"2013","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Springer, Berlin (2013)"},{"issue":"8","key":"1001_CR14","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. Discrete Math. 339(8), 2157\u20132167 (2016). https:\/\/doi.org\/10.1016\/j.disc.2016.03.011","journal-title":"Discrete Math."},{"issue":"2","key":"1001_CR15","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1002\/jgt.3190110205","volume":"11","author":"P Erd\u0151s","year":"1987","unstructured":"Erd\u0151s, P., Hare, W.R., Hedetniemi, S.T., Laskar, R.: On the equality of the Grundy and ochromatic numbers of a graph. J. Graph Theory 11(2), 157\u2013159 (1987)","journal-title":"J. Graph Theory"},{"issue":"1","key":"1001_CR16","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/S0012-365X(03)00184-5","volume":"272","author":"P Erd\u0151s","year":"2003","unstructured":"Erd\u0151s, P., Hedetniemi, S.T., Laskar, R.C., Prins, G.C.E.: On the equality of the partial Grundy and upper ochromatic numbers of graphs. Discrete Math. 272(1), 53\u201364 (2003). (In Honor of Frank Harary)","journal-title":"Discrete Math."},{"doi-asserted-by":"crossref","unstructured":"Erd\u00f6s, P.: Some combinatorial, geometric and set theoretic problems in measure theory. In: Measure Theory Oberwolfach 1983, pp. 321\u2013327. Springer (1984)","key":"1001_CR17","DOI":"10.1007\/BFb0072626"},{"doi-asserted-by":"publisher","unstructured":"Feldmann, A.E., Marx, D.: The parameterized hardness of the k-center problem in transportation networks. In: 16th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2018, June 18\u201320, 2018, Malm\u00f6, Sweden, pp. 19:1\u201319:13 (2018). https:\/\/doi.org\/10.4230\/LIPIcs.SWAT.2018.19","key":"1001_CR18","DOI":"10.4230\/LIPIcs.SWAT.2018.19"},{"key":"1001_CR19","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, New York (1979)"},{"unstructured":"Gastineau, N.: Partitionnement, recouvrement et colorabilit\u00e9 dans les graphes. (Partitionability, coverability and colorability in graphs). PhD thesis, University of Burgundy, Dijon, France (2014). https:\/\/tel.archives-ouvertes.fr\/tel-01136691","key":"1001_CR20"},{"issue":"3","key":"1001_CR21","doi-asserted-by":"publisher","first-page":"17:1","DOI":"10.1145\/3051095","volume":"64","author":"M Grohe","year":"2017","unstructured":"Grohe, M., Kreutzer, S., Siebertz, S.: Deciding first-order properties of nowhere dense graphs. J. ACM 64(3), 17:1-17:32 (2017). https:\/\/doi.org\/10.1145\/3051095","journal-title":"J. ACM"},{"key":"1001_CR22","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":"1\u20133","key":"1001_CR23","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/S0012-365X(96)00359-7","volume":"177","author":"A Gy\u00e1rf\u00e1s","year":"1997","unstructured":"Gy\u00e1rf\u00e1s, A., Kir\u00e1ly, Z., Lehel, J.: On-line 3-chromatic graphs-II critical graphs. Discrete Math. 177(1\u20133), 99\u2013122 (1997)","journal-title":"Discrete Math."},{"issue":"1","key":"1001_CR24","doi-asserted-by":"publisher","first-page":"18:1","DOI":"10.1186\/s13173-015-0036-x","volume":"21","author":"F Havet","year":"2015","unstructured":"Havet, F., Maia, A.K., Min-Li, Yu.: Complexity of greedy edge-colouring. J. Braz. Comput. Soc. 21(1), 18:1-18:7 (2015). https:\/\/doi.org\/10.1186\/s13173-015-0036-x","journal-title":"J. Braz. Comput. Soc."},{"issue":"4","key":"1001_CR25","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":"1001_CR26","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. Congr. Numer. 36, 351\u2013363 (1982)","journal-title":"Congr. Numer."},{"issue":"4","key":"1001_CR27","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? J. Comput. Syst. Sci. 63(4), 512\u2013530 (2001)","journal-title":"J. Comput. Syst. Sci."},{"key":"1001_CR28","first-page":"41","volume":"105","author":"D Lokshtanov","year":"2011","unstructured":"Lokshtanov, D., Marx, D., Saurabh, S.: Lower bounds based on the exponential time hypothesis. Bull. EATCS 105, 41\u201372 (2011)","journal-title":"Bull. EATCS"},{"doi-asserted-by":"publisher","unstructured":"Marx, D.: Parameterized complexity of independence and domination on geometric graphs. In: Parameterized and Exact Computation, Second International Workshop, IWPEC 2006, Z\u00fcrich, Switzerland, September 13\u201315, 2006, Proceedings, pp. 154\u2013165 (2006). https:\/\/doi.org\/10.1007\/11847250_14","key":"1001_CR29","DOI":"10.1007\/11847250_14"},{"doi-asserted-by":"publisher","unstructured":"Marx, D\u00e1niel: On the optimality of planar and geometric approximation schemes. In: 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), October 20\u201323, 2007, Providence, RI, USA, Proceedings, pp. 338\u2013348 (2007). https:\/\/doi.org\/10.1109\/FOCS.2007.50","key":"1001_CR30","DOI":"10.1109\/FOCS.2007.50"},{"issue":"1","key":"1001_CR31","doi-asserted-by":"publisher","first-page":"85","DOI":"10.4086\/toc.2010.v006a005","volume":"6","author":"D Marx","year":"2010","unstructured":"Marx, D.: Can you beat treewidth? Theory Comput. 6(1), 85\u2013112 (2010). https:\/\/doi.org\/10.4086\/toc.2010.v006a005","journal-title":"Theory Comput."},{"doi-asserted-by":"crossref","unstructured":"Marx, D., Pilipczuk, M.: Optimal parameterized algorithms for planar facility location problems using voronoi diagrams. CoRR (2015). arXiv:1504.05476","key":"1001_CR32","DOI":"10.1007\/978-3-662-48350-3_72"},{"doi-asserted-by":"publisher","unstructured":"Marx, D., Pilipczuk, M.: Optimal parameterized algorithms for planar facility location problems using voronoi diagrams. In: Algorithms-ESA 2015-23rd Annual European Symposium, Patras, Greece, September 14\u201316, 2015, Proceedings, pp. 865\u2013877 (2015). https:\/\/doi.org\/10.1007\/978-3-662-48350-3_72","key":"1001_CR33","DOI":"10.1007\/978-3-662-48350-3_72"},{"doi-asserted-by":"publisher","unstructured":"Naor, M., Schulman, L.J., Srinivasan, A.: Splitters and near-optimal derandomization. In: 36th Annual Symposium on Foundations of Computer Science, Milwaukee, Wisconsin, USA, 23\u201325 October 1995, pp. 182\u2013191. IEEE Computer Society (1995). https:\/\/doi.org\/10.1109\/SFCS.1995.492475","key":"1001_CR34","DOI":"10.1109\/SFCS.1995.492475"},{"key":"1001_CR35","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1016\/j.jcss.2016.09.012","volume":"84","author":"F Panolan","year":"2017","unstructured":"Panolan, F., Philip, G., Saurabh, S.: On the parameterized complexity of b-chromatic number. J. Comput. Syst. Sci. 84, 120\u2013131 (2017). https:\/\/doi.org\/10.1016\/j.jcss.2016.09.012","journal-title":"J. Comput. Syst. Sci."},{"unstructured":"Sampaio, L.: Algorithmic Aspects of Graph Colouring Heuristics. PhD thesis, University of Nice-Sophia Antipolis, November (2012)","key":"1001_CR36"},{"issue":"6","key":"1001_CR37","first-page":"2","volume":"11","author":"GJ Simmons","year":"1982","unstructured":"Simmons, G.J.: The ochromatic number of graphs. Graph Theory Newsl. 11(6), 2\u20133 (1982)","journal-title":"Graph Theory Newsl."},{"issue":"4","key":"1001_CR38","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 J. Discrete Math. 10(4), 529\u2013550 (1997)","journal-title":"SIAM J. Discrete Math."},{"doi-asserted-by":"publisher","unstructured":"Telle, J.A., Villanger, Y.: FPT algorithms for domination in biclique-free graphs. In: Epstein, L., Ferragina, P. (eds.) Algorithms-ESA 2012-20th Annual European Symposium, Ljubljana, Slovenia, September 10\u201312, 2012. Proceedings, Volume 7501 of Lecture Notes in Computer Science, pp. 802\u2013812. Springer (2012). https:\/\/doi.org\/10.1007\/978-3-642-33090-2_69","key":"1001_CR39","DOI":"10.1007\/978-3-642-33090-2_69"},{"key":"1001_CR40","first-page":"325","volume":"31","author":"M Zaker","year":"2005","unstructured":"Zaker, M.: The Grundy chromatic number of the complement of bipartite graphs. Australas. J. Comb. 31, 325\u2013329 (2005)","journal-title":"Australas. J. Comb."},{"issue":"23","key":"1001_CR41","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 Math. 306(23), 3166\u20133173 (2006)","journal-title":"Discrete Math."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01001-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-01001-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01001-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,18]],"date-time":"2023-01-18T12:04:54Z","timestamp":1674043494000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-01001-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,16]]},"references-count":41,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,1]]}},"alternative-id":["1001"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-01001-2","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2022,7,16]]},"assertion":[{"value":"3 September 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 June 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 July 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}