{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,14]],"date-time":"2026-02-14T04:18:40Z","timestamp":1771042720219,"version":"3.50.1"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2022,12,20]],"date-time":"2022-12-20T00:00:00Z","timestamp":1671494400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,12,20]],"date-time":"2022-12-20T00:00:00Z","timestamp":1671494400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100002322","name":"Coordena\u00e7\u00e3o de Aperfei\u00e7oamento de Pessoal de N\u00edvel Superior","doi-asserted-by":"publisher","award":["Finance Code 001"],"award-info":[{"award-number":["Finance Code 001"]}],"id":[{"id":"10.13039\/501100002322","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003593","name":"Conselho Nacional de Desenvolvimento Cient\u00edfico e Tecnol\u00f3gico","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2023,7]]},"DOI":"10.1007\/s00453-022-01085-w","type":"journal-article","created":{"date-parts":[[2022,12,20]],"date-time":"2022-12-20T12:03:39Z","timestamp":1671537819000},"page":"1912-1947","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Structural Parameterizations for Equitable Coloring: Complexity, FPT Algorithms, and Kernelization"],"prefix":"10.1007","volume":"85","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5164-1460","authenticated-orcid":false,"given":"Guilherme C. M.","family":"Gomes","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Matheus R.","family":"Guedes","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vinicius F.","family":"dos Santos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,12,20]]},"reference":[{"issue":"2","key":"1085_CR1","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1016\/0304-3975(96)00031-X","volume":"162","author":"BS Baker","year":"1996","unstructured":"Baker, B.S., Coffman, E.G.: Mutual exclusion scheduling. Theor. Comput. Sci. 162(2), 225\u2013243 (1996)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"1085_CR2","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1016\/j.tcs.2005.09.027","volume":"349","author":"HL Bodlaender","year":"2005","unstructured":"Bodlaender, H.L., Fomin, F.V.: Equitable colorings of bounded treewidth graphs. Theor. Comput. Sci. 349(1), 22\u201330 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"1085_CR3","unstructured":"Bodlaender, H.L., Jansen, B.M.P., Kratsch, S.: Cross-composition: a new technique for kernelization lower bounds. In: Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science (STACS), LIPIcs, vol. 9, pp. 165\u2013176 (2011)"},{"issue":"1","key":"1085_CR4","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/0304-3975(95)00057-4","volume":"148","author":"HL Bodlaender","year":"1995","unstructured":"Bodlaender, H.L., Jansen, K.: Restrictions of graph partition problems. Part I. Theor. Comput. Sci. 148(1), 93\u2013109 (1995)","journal-title":"Theor. Comput. Sci."},{"key":"1085_CR5","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-349-03521-2","volume-title":"Graph Theory with Applications","author":"JA Bondy","year":"1976","unstructured":"Bondy, J.A., Murty, U.S.R.: Graph Theory with Applications, vol. 290. Macmillan, London (1976)"},{"key":"1085_CR6","doi-asserted-by":"crossref","unstructured":"Boral, A., Cygan, M., Kociumaka, T., Pilipczuk, M.: Fast branching algorithm for cluster vertex deletion (2013). CoRR, arXiv:1306.3877","DOI":"10.1007\/978-3-319-06686-8_9"},{"issue":"3","key":"1085_CR7","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1016\/S0166-218X(02)00242-1","volume":"127","author":"L Cai","year":"2003","unstructured":"Cai, L.: Parameterized complexity of vertex colouring. Discret. Appl. Math. 127(3), 415\u2013429 (2003)","journal-title":"Discret. Appl. Math."},{"key":"1085_CR8","doi-asserted-by":"crossref","unstructured":"Cappelle, M.R., Gomes, G., Santos, V.F.D.: Parameterized algorithms for locating-dominating sets (2020)","DOI":"10.1016\/j.procs.2021.11.012"},{"key":"1085_CR9","first-page":"1","volume-title":"Equitable and $$m$$-bounded coloring of split graphs","author":"B-L Chen","year":"1996","unstructured":"Chen, B.-L., Ko, M.-T., Lih, K.-W.: Equitable and $$m$$-bounded coloring of split graphs, pp. 1\u20135. Springer, Berlin (1996)"},{"key":"1085_CR10","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/978-3-030-48966-3_15","volume-title":"Combinatorial Algorithms","author":"G Cordasco","year":"2020","unstructured":"Cordasco, G., Gargano, L., Rescigno, A.A.: Iterated type partitions. In: G\u0105sieniec, L., Klasing, R., Radzik, T. (eds.) Combinatorial Algorithms, pp. 195\u2013210. Springer, Cham (2020)"},{"key":"1085_CR11","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. The MIT Press (2009)"},{"key":"1085_CR12","doi-asserted-by":"crossref","unstructured":"Cygan, M., Fomin, F.\u00a0V., Kowalik, \u0141., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms, vol.\u00a03. Springer (2015)","DOI":"10.1007\/978-3-319-21275-3_1"},{"key":"1085_CR13","doi-asserted-by":"publisher","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","volume":"17","author":"J Edmonds","year":"1965","unstructured":"Edmonds, J.: Paths, trees, and flowers. Can. J. Math. 17, 449\u2013467 (1965)","journal-title":"Can. J. Math."},{"key":"1085_CR14","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1007\/978-3-642-11269-0_10","volume-title":"Parameterized and Exact Computation","author":"R Enciso","year":"2009","unstructured":"Enciso, R., Fellows, M.R., Guo, J., Kanj, I., Rosamond, F., Such\u00fd, O.: What makes equitable connected partition easy. In: Chen, J., Fomin, F.V. (eds.) Parameterized and Exact Computation, pp. 122\u2013133. Springer, Berlin (2009)"},{"key":"1085_CR15","unstructured":"Estivill-Castro, V., Fellows, M., Langston, M., Rosamond, F.: FPT is P-Time Extremal Structure I (Fixed-parameter tractability is polynomial-time extremal structure theory), pp. 1\u201341. King\u2019s College Publications (2005)"},{"issue":"2","key":"1085_CR16","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/j.ic.2010.11.026","volume":"209","author":"MR Fellows","year":"2011","unstructured":"Fellows, M.R., Fomin, F.V., Lokshtanov, D., Rosamond, F., Saurabh, S., Szeider, S., Thomassen, C.: On the complexity of some colorful problems parameterized by treewidth. Inf. Comput. 209(2), 143\u2013153 (2011)","journal-title":"Inf. Comput."},{"issue":"23","key":"1085_CR17","doi-asserted-by":"publisher","first-page":"2513","DOI":"10.1016\/j.tcs.2010.10.043","volume":"412","author":"J Fiala","year":"2011","unstructured":"Fiala, J., Golovach, P.A., Kratochv\u00edl, J.: Parameterized complexity of coloring problems: treewidth versus vertex cover. Theor. Comput. Sci. 412(23), 2513\u20132523 (2011). (Theory and Applications of Models of Computation (TAMC 2009))","journal-title":"Theor. Comput. Sci."},{"key":"1085_CR18","doi-asserted-by":"crossref","unstructured":"Ganian, R.: Improving vertex cover as a graph parameter. Discrete Math. Theor. Comput. Sci. 17(2) (2015)","DOI":"10.46298\/dmtcs.2136"},{"key":"1085_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 & Co., New York (1979)"},{"key":"1085_CR20","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1007\/978-3-030-61792-9_11","volume-title":"LATIN 2020: Theoretical Informatics","author":"GCM Gomes","year":"2020","unstructured":"Gomes, G.C.M., Guedes, M.R., dos Santos, V.F.: Structural parameterizations for equitable coloring. In: Kohayakawa, Y., Miyazawa, F.K. (eds.) LATIN 2020: Theoretical Informatics, pp. 129\u2013140. Springer, Cham (2020)"},{"key":"1085_CR21","unstructured":"Gomes, G., Lima, C.V.G.C., Santos, V.F.D.: Parameterized Complexity of Equitable Coloring. Discrete Math. Theor. Comput. Sci. 21(1), ICGT 2018 (2019)"},{"key":"1085_CR22","first-page":"601","volume":"2","author":"A Hajnal","year":"1970","unstructured":"Hajnal, A., Szemer\u00e9di, E.: Proof of a conjecture of P. Erdos. Combin. Theory Appl. 2, 601\u2013623 (1970)","journal-title":"Combin. Theory Appl."},{"key":"1085_CR23","unstructured":"Irani, S., Leung, V.: Scheduling with conflicts, and applications to traffic signal control. In: Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201996, pp. 85-94. Society for Industrial and Applied Mathematics (1996)"},{"key":"1085_CR24","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1016\/j.ic.2013.08.005","volume":"231","author":"BM Jansen","year":"2013","unstructured":"Jansen, B.M., Kratsch, S.: Data reduction for graph coloring problems. Inf. Comput. 231, 70\u201388 (2013). (Fundamentals of Computation Theory)","journal-title":"Inf. Comput."},{"issue":"1\u20133","key":"1085_CR25","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1016\/S0012-365X(00)00345-9","volume":"232","author":"M Jarvis","year":"2001","unstructured":"Jarvis, M., Zhou, B.: Bounded vertex coloring of trees. Discret. Math. 232(1\u20133), 145\u2013151 (2001)","journal-title":"Discret. Math."},{"issue":"2","key":"1085_CR26","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/s00493-010-2483-5","volume":"30","author":"HA Kierstead","year":"2010","unstructured":"Kierstead, H.A., Kostochka, A.V., Mydlarz, M., Szemer\u00e9di, E.: A fast algorithm for equitable coloring. Combinatorica 30(2), 217\u2013224 (2010)","journal-title":"Combinatorica"},{"issue":"4","key":"1085_CR27","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1287\/moor.8.4.538","volume":"8","author":"HW Lenstra","year":"1983","unstructured":"Lenstra, H.W.: Integer programming with a fixed number of variables. Math. Oper. Res. 8(4), 538\u2013548 (1983)","journal-title":"Math. Oper. Res."},{"key":"1085_CR28","doi-asserted-by":"crossref","unstructured":"Lih, K.-W.: Equitable coloring of graphs. In: Handbook of Combinatorial Optimization, pp. 1199\u20131248. Springer (2013)","DOI":"10.1007\/978-1-4419-7997-1_25"},{"issue":"8","key":"1085_CR29","doi-asserted-by":"publisher","first-page":"920","DOI":"10.1080\/00029890.1973.11993408","volume":"80","author":"W Meyer","year":"1973","unstructured":"Meyer, W.: Equitable coloring. Am. Math. Mon. 80(8), 920\u2013922 (1973)","journal-title":"Am. Math. Mon."},{"key":"1085_CR30","unstructured":"Reddy, I.V.: Parameterized coloring problems on threshold graphs (2019)"},{"key":"1085_CR31","unstructured":"Smith, B., Bjorstad, P., Gropp, W.: Domain Decomposition: Parallel Multilevel Methods for Elliptic Partial Differential Equations. Cambridge University Press (2004)"},{"key":"1085_CR32","unstructured":"Sorge, M., Weller, M.: The graph parameter hierarchy. Unpublished manuscript (2019)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01085-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-01085-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01085-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,10]],"date-time":"2024-10-10T19:44:12Z","timestamp":1728589452000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-01085-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12,20]]},"references-count":32,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2023,7]]}},"alternative-id":["1085"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-01085-w","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,12,20]]},"assertion":[{"value":"10 May 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 December 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 December 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}