{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,19]],"date-time":"2025-12-19T21:10:58Z","timestamp":1766178658883,"version":"3.37.3"},"reference-count":59,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2023,9,23]],"date-time":"2023-09-23T00:00:00Z","timestamp":1695427200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,9,23]],"date-time":"2023-09-23T00:00:00Z","timestamp":1695427200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"University of Bergen"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2024,8]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We provide a polynomial-time algorithm for  <jats:italic>b<\/jats:italic><jats:sc>-Coloring<\/jats:sc> on graphs of constant clique-width. This unifies and extends nearly all previously known polynomial time results on graph classes, and answers open questions posed by Campos and Silva (Algorithmica <jats:bold>80<\/jats:bold>(1), 104\u2013115, 2018) and Bonomo et al. (Graphs and Combinatorics <jats:bold>25<\/jats:bold>(2), 153\u2013167, 2009). This constitutes the first result concerning structural parameterizations of this problem. We show that the problem is <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\textsf{FPT}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>FPT<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> when parameterized by the vertex cover number on general graphs, and on chordal graphs when parameterized by the number of colors. Additionally, we observe that our algorithm for graphs of bounded clique-width can be adapted to solve the <jats:sc>Fall Coloring<\/jats:sc> problem within the same runtime bound. The running times of the clique-width based algorithms for <jats:inline-formula><jats:alternatives><jats:tex-math>$$b$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>b<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-<jats:sc>Coloring<\/jats:sc> and <jats:sc>Fall Coloring<\/jats:sc> are tight under the Exponential Time Hypothesis.<\/jats:p>","DOI":"10.1007\/s00224-023-10132-0","type":"journal-article","created":{"date-parts":[[2023,9,23]],"date-time":"2023-09-23T09:02:07Z","timestamp":1695459727000},"page":"1049-1081","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["b-Coloring Parameterized by Clique-Width"],"prefix":"10.1007","volume":"68","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4856-5863","authenticated-orcid":false,"given":"Lars","family":"Jaffke","sequence":"first","affiliation":[]},{"given":"Paloma T.","family":"Lima","sequence":"additional","affiliation":[]},{"given":"Daniel","family":"Lokshtanov","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,9,23]]},"reference":[{"key":"10132_CR1","unstructured":"Aboulker, P., Bonnet, \u00c9., Kim, E.J., Sikora, F.: Grundy coloring & friends, half-graphs, bicliques. In: STACS 2020, LIPIcs, vol. 154, pp. 58:1\u201358:18 (2020)"},{"key":"10132_CR2","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1016\/0095-8956(86)90043-2","volume":"41","author":"HJ Bandelt","year":"1986","unstructured":"Bandelt, H.J., Mulder, H.M.: Distance-hereditary graphs. J. Comb. Theory. Ser. B 41, 182\u2013208 (1986)","journal-title":"J. Comb. Theory. Ser. B"},{"key":"10132_CR3","unstructured":"Belmonte, R., Kim, E.J., Lampis, M., Mitsou, V., Otachi, Y.: Grundy distinguishes treewidth from pathwidth. In: ESA 2020, LIPIcs, vol. 173, pp. 14:1\u201314:19 (2020)"},{"key":"10132_CR4","doi-asserted-by":"crossref","unstructured":"Blair, J.R., Peyton, B.: An introduction to chordal graphs and clique trees. In: Graph theory and sparse matrix computation, pp. 1\u201329. Springer, (1993)","DOI":"10.1007\/978-1-4613-8369-7_1"},{"issue":"2","key":"10132_CR5","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1007\/s00373-008-0829-1","volume":"25","author":"F Bonomo","year":"2009","unstructured":"Bonomo, F., Dur\u00e1n, G., Maffray, F., Marenco, J., Valencia-Pabon, M.: On the b-coloring of cographs and $$P_4$$-sparse graphs. Graphs and Combinatorics 25(2), 153\u2013167 (2009)","journal-title":"Graphs and Combinatorics"},{"issue":"2","key":"10132_CR6","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1007\/s00453-014-9921-5","volume":"73","author":"F Bonomo","year":"2015","unstructured":"Bonomo, F., Schaudt, O., Stein, M., Valencia-Pabon, M.: b-Coloring is NP-hard on co-bipartite graphs and polytime solvable on tree-cographs. Algorithmica 73(2), 289\u2013305 (2015)","journal-title":"Algorithmica"},{"key":"10132_CR7","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1016\/j.tcs.2013.01.009","volume":"511","author":"B Bui-Xuan","year":"2013","unstructured":"Bui-Xuan, B., Telle, J.A., Vatshelle, M.: Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems. Theor. Comput. Sci. 511, 66\u201376 (2013). https:\/\/doi.org\/10.1016\/j.tcs.2013.01.009","journal-title":"Theor. Comput. Sci."},{"issue":"11","key":"10132_CR8","doi-asserted-by":"publisher","first-page":"2072","DOI":"10.1016\/j.disc.2015.04.026","volume":"338","author":"VA Campos","year":"2015","unstructured":"Campos, V.A., Lima, C.V., Martins, N.A., Sampaio, L., Santos, M.C., Silva, A.: The b-chromatic index of graphs. Discrete Mathematics 338(11), 2072\u20132079 (2015)","journal-title":"Discrete Mathematics"},{"key":"10132_CR9","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1016\/j.ejc.2015.02.017","volume":"48","author":"VA Campos","year":"2015","unstructured":"Campos, V.A., Lima, C.V.G.C., Silva, A.: Graphs of girth at least 7 have high b-chromatic number. European J. Comb. 48, 154\u2013164 (2015)","journal-title":"European J. Comb."},{"key":"10132_CR10","doi-asserted-by":"publisher","first-page":"539","DOI":"10.1016\/j.dam.2013.10.031","volume":"164","author":"VA Campos","year":"2014","unstructured":"Campos, V.A., Linhares-Sales, C., Sampaio, R., Maia, A.K.: Maximization coloring problems on graphs with few $$P_4$$. Discret Appl. Math. 164, 539\u2013546 (2014)","journal-title":"Discret Appl. Math."},{"issue":"1","key":"10132_CR11","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1007\/s00453-016-0240-x","volume":"80","author":"VA Campos","year":"2018","unstructured":"Campos, V.A., Silva, A.: Edge-b-coloring trees. Algorithmica 80(1), 104\u2013115 (2018)","journal-title":"Algorithmica"},{"issue":"40\u201342","key":"10132_CR12","doi-asserted-by":"publisher","first-page":"3736","DOI":"10.1016\/j.tcs.2010.06.026","volume":"411","author":"J Chen","year":"2010","unstructured":"Chen, J., Kanj, I.A., Xia, G.: Improved upper bounds for vertex cover. Theor. Comput. Sci. 411(40\u201342), 3736\u20133756 (2010). https:\/\/doi.org\/10.1016\/j.tcs.2010.06.026","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"10132_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3310228","volume":"15","author":"D Coudert","year":"2019","unstructured":"Coudert, D., Ducoffe, G., Popa, A.: Fully polynomial FPT algorithms for some classes of bounded clique-width graphs. ACM Trans. Algorithm 15(3), 1\u201357 (2019)","journal-title":"ACM Trans. Algorithm"},{"key":"10132_CR14","unstructured":"Courcelle, B., Durand, I., Raskin, M.: A unified algorithm for colouring graphs of bounded clique-width. CoRR (2020). arXiv:2008.07468"},{"issue":"2","key":"10132_CR15","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1016\/0022-0000(93)90004-G","volume":"46","author":"B Courcelle","year":"1993","unstructured":"Courcelle, B., Engelfriet, J., Rozenberg, G.: Handle-rewriting hypergraph grammars. J. Comput. Syst. Sci. 46(2), 218\u2013270 (1993)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1\u20133","key":"10132_CR16","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/S0166-218X(99)00184-5","volume":"101","author":"B Courcelle","year":"2000","unstructured":"Courcelle, B., Olariu, S.: Upper bounds to the clique width of graphs. Discret. Appl. Math. 101(1\u20133), 77\u2013114 (2000)","journal-title":"Discret. Appl. Math."},{"key":"10132_CR17","doi-asserted-by":"crossref","unstructured":"Cygan, M., Fomin, F.V., Kowalik, \u0141., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer (2015)","DOI":"10.1007\/978-3-319-21275-3"},{"key":"10132_CR18","doi-asserted-by":"crossref","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Springer (2013)","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"10132_CR19","first-page":"257","volume":"33","author":"JE Dunbar","year":"2000","unstructured":"Dunbar, J.E., Hedetniemi, S.M., Hedetniemi, S., Jacobs, D.P., Knisely, J., Laskar, R., Rall, D.F.: Fall colorings of graphs. J. Comb. Math. Comb. Comput. 33, 257\u2013274 (2000)","journal-title":"J. Comb. Math. Comb. Comput."},{"issue":"8","key":"10132_CR20","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(8), 2157\u20132167 (2016)","journal-title":"Discret. Math."},{"key":"10132_CR21","doi-asserted-by":"crossref","unstructured":"Espelage, W., Gurski, F., Wanke, E.: How to solve NP-hard graph problems on clique-width bounded graphs in polynomial time. In: WG 2001, pp. 117\u2013128 (2001)","DOI":"10.1007\/3-540-45477-2_12"},{"key":"10132_CR22","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1016\/j.endm.2004.03.030","volume":"17","author":"T Faik","year":"2004","unstructured":"Faik, T.: About the $$b$$-continuity of graphs (extended abstract). Electron. Notes Discrete Math. 17, 151\u2013156 (2004)","journal-title":"Electron. Notes Discrete Math."},{"issue":"5","key":"10132_CR23","doi-asserted-by":"publisher","first-page":"1941","DOI":"10.1137\/080742270","volume":"39","author":"FV Fomin","year":"2010","unstructured":"Fomin, F.V., Golovach, P.A., Lokshtanov, D., Saurabh, S.: Intractability of clique-width parameterizations. SIAM J. Comput. 39(5), 1941\u20131956 (2010)","journal-title":"SIAM J. Comput."},{"key":"10132_CR24","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Golovach, P.A., Lokshtanov, D., Saurabh, S., Zehavi, M.: Clique-width III: Hamiltonian cycle and the odd case of graph coloring. ACM Trans. Algorithms 15(1), 9:1\u20139:27 (2019)","DOI":"10.1145\/3280824"},{"issue":"1\u20133","key":"10132_CR25","doi-asserted-by":"publisher","first-page":"719","DOI":"10.1016\/S0304-3975(02)00725-9","volume":"299","author":"MU Gerber","year":"2003","unstructured":"Gerber, M.U., Kobler, D.: Algorithms for vertex-partitioning problems on graphs with fixed clique-width. Theor. Comput. Sci. 299(1\u20133), 719\u2013734 (2003). https:\/\/doi.org\/10.1016\/S0304-3975(02)00725-9","journal-title":"Theor. Comput. Sci."},{"issue":"7","key":"10132_CR26","doi-asserted-by":"publisher","first-page":"839","DOI":"10.1016\/j.disc.2012.11.031","volume":"313","author":"W Goddard","year":"2013","unstructured":"Goddard, W., Henning, M.A.: Independent domination in graphs: A survey and recent results. Discret. Math. 313(7), 839\u2013854 (2013)","journal-title":"Discret. Math."},{"issue":"03","key":"10132_CR27","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1142\/S0129054100000260","volume":"11","author":"MC Golumbic","year":"2000","unstructured":"Golumbic, M.C., Rotics, U.: On the clique-width of some perfect graph classes. Int. J. Found. Comput. Sci. 11(03), 423\u2013443 (2000)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"2","key":"10132_CR28","doi-asserted-by":"publisher","first-page":"346","DOI":"10.1007\/s00224-016-9685-1","volume":"60","author":"F Gurski","year":"2017","unstructured":"Gurski, F.: The behavior of clique-width under graph operations and graph transformations. Theory Comput. Syst. 60(2), 346\u2013376 (2017). https:\/\/doi.org\/10.1007\/s00224-016-9685-1","journal-title":"Theory Comput. Syst."},{"issue":"18","key":"10132_CR29","doi-asserted-by":"publisher","first-page":"2709","DOI":"10.1016\/j.dam.2011.10.017","volume":"160","author":"F Havet","year":"2012","unstructured":"Havet, F., Sales, C.L., Sampaio, L.: b-coloring of tight graphs. Discret. Appl. Math. 160(18), 2709\u20132715 (2012)","journal-title":"Discret. Appl. Math."},{"key":"10132_CR30","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"},{"issue":"2","key":"10132_CR31","first-page":"128","volume":"5","author":"P Heggernes","year":"1998","unstructured":"Heggernes, P., Telle, J.A.: Partitioning graphs into generalized dominating sets. Nord. J. Comput. 5(2), 128\u2013142 (1998)","journal-title":"Nord. J. Comput."},{"issue":"2","key":"10132_CR32","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1006\/jcss.2000.1727","volume":"62","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R.: On the complexity of $$k$$-SAT. J. Comput. Syst. Sci. 62(2), 367\u2013375 (2001)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"10132_CR33","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."},{"issue":"1\u20133","key":"10132_CR34","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(1\u20133), 127\u2013141 (1999)","journal-title":"Discret. Appl. Math."},{"key":"10132_CR35","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1016\/j.tcs.2020.02.007","volume":"815","author":"L Jaffke","year":"2020","unstructured":"Jaffke, L., Lima, P.T.: A complexity dichotomy for critical values of the b-chromatic number of graphs. Theor. Comput. Sci. 815, 182\u2013196 (2020)","journal-title":"Theor. Comput. Sci."},{"key":"10132_CR36","unstructured":"Jaffke, L., Lima, P.T., Lokshtanov, D.: b-Coloring parameterized by clique-width. In: STACS 2021, LIPIcs, vol. 187, pp. 43:1\u201343:15. Schloss Dagstuhl (2021)"},{"key":"10132_CR37","doi-asserted-by":"publisher","unstructured":"Jaffke, L., Lima, P.T., Philip, G.: Structural parameterizations of clique coloring. In: MFCS 2020, LIPIcs, vol. 170, pp. 49:1\u201349:15. Schloss Dagstuhl (2020). https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2020.49. https:\/\/drops.dagstuhl.de\/opus\/volltexte\/2020\/12715","DOI":"10.4230\/LIPIcs.MFCS.2020.49"},{"key":"10132_CR38","doi-asserted-by":"crossref","unstructured":"Jansen, K.: Complexity results for the optimum cost chromatic partition problem (1997)","DOI":"10.1007\/3-540-62592-5_58"},{"key":"10132_CR39","doi-asserted-by":"publisher","unstructured":"Kloks, T.: Treewidth, Computations and Approximations, LNCS, vol. 842.Springer (1994). https:\/\/doi.org\/10.1007\/BFb0045375","DOI":"10.1007\/BFb0045375"},{"key":"10132_CR40","doi-asserted-by":"publisher","unstructured":"Korhonen, T.: A single-exponential time 2-approximation algorithm for treewidth. In: FOCS 2021, pp. 184\u2013192. IEEE (2021). https:\/\/doi.org\/10.1109\/FOCS52979.2021.00026","DOI":"10.1109\/FOCS52979.2021.00026"},{"key":"10132_CR41","doi-asserted-by":"crossref","unstructured":"Kratochv\u00edl, J., Tuza, Z., Voigt, M.: On the b-chromatic number of graphs. In: WG 2002, pp. 310\u2013320 (2002)","DOI":"10.1007\/3-540-36379-3_27"},{"issue":"3","key":"10132_CR42","doi-asserted-by":"publisher","first-page":"1538","DOI":"10.1137\/19M1280326","volume":"34","author":"M Lampis","year":"2020","unstructured":"Lampis, M.: Finer tight bounds for coloring on clique-width. SIAM J. Discret. Math. 34(3), 1538\u20131558 (2020). https:\/\/doi.org\/10.1137\/19M1280326","journal-title":"SIAM J. Discret. Math."},{"issue":"2","key":"10132_CR43","doi-asserted-by":"publisher","first-page":"330","DOI":"10.1016\/j.dam.2008.03.003","volume":"157","author":"R Laskar","year":"2009","unstructured":"Laskar, R., Lyle, J.: Fall colouring of bipartite graphs and cartesian products of graphs. Discret. Appl. Math. 157(2), 330\u2013338 (2009)","journal-title":"Discret. Appl. Math."},{"key":"10132_CR44","doi-asserted-by":"crossref","unstructured":"Lauri, J., Mitillos, C.: Complexity of fall coloring for restricted graph classes. In: IWOCA 2019, pp. 352\u2013364. Springer (2019)","DOI":"10.1007\/978-3-030-25005-8_29"},{"key":"10132_CR45","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. Bulletin of the EATCS 105, 41\u201372 (2011)","journal-title":"Bulletin of the EATCS"},{"issue":"3","key":"10132_CR46","doi-asserted-by":"publisher","first-page":"675","DOI":"10.1137\/16M1104834","volume":"47","author":"D Lokshtanov","year":"2018","unstructured":"Lokshtanov, D., Marx, D., Saurabh, S.: Slightly superexponential parameterized problems. SIAM J. Comput. 47(3), 675\u2013702 (2018)","journal-title":"SIAM J. Comput."},{"key":"10132_CR47","first-page":"149","volume":"172","author":"J Lyle","year":"2005","unstructured":"Lyle, J., Drake, N., Laskar, R.: Independent domatic partitioning or fall coloring of strongly chordal graphs. Congressus Numerantium 172, 149\u2013159 (2005)","journal-title":"Congressus Numerantium"},{"issue":"03","key":"10132_CR48","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1142\/S0129054199000241","volume":"10","author":"JA Makowsky","year":"1999","unstructured":"Makowsky, J.A., Rotics, U.: On the clique-width of graphs with few $$P_4$$\u2019s. Int. J. Found. Comput. Sci. 10(03), 329\u2013348 (1999)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"10132_CR49","unstructured":"Mitillos, C.: Topics in graph fall-coloring. Ph.D. thesis, Illinois Institute of Technology (2016)"},{"key":"10132_CR50","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)","journal-title":"J. Comput. Syst. Sci."},{"key":"10132_CR51","unstructured":"Rao, M.: D\u00e9compositions de graphes et algorithmes efficaces. Ph.D. thesis, University of Metz (2006)"},{"issue":"24","key":"10132_CR52","doi-asserted-by":"publisher","first-page":"6157","DOI":"10.1016\/j.disc.2007.11.039","volume":"308","author":"M Rao","year":"2008","unstructured":"Rao, M.: Clique-width of graphs defined by one-vertex extensions. Discret. Math. 308(24), 6157\u20136165 (2008)","journal-title":"Discret. Math."},{"key":"10132_CR53","unstructured":"Sampaio, L.: Algorithmic aspects of graph colourings heuristics. Ph.D. thesis, Universit\u00e9 Nice Sophia Antipolis (2012)"},{"key":"10132_CR54","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1016\/j.dam.2018.06.037","volume":"254","author":"A Silva","year":"2019","unstructured":"Silva, A.: Graphs with small fall-spectrum. Discret Appl Math 254, 183\u2013188 (2019)","journal-title":"Discret Appl Math"},{"key":"10132_CR55","unstructured":"Silva, A.S.F.D.: The b-chromatic number of some tree-like graphs. Ph.D. thesis, Universit\u00e9 Joseph-Fourier - Grenoble I (2010)"},{"issue":"4","key":"10132_CR56","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. Discret. Mathematics 10(4), 529\u2013550 (1997)","journal-title":"SIAM J. Discret. Mathematics"},{"issue":"1\u20133","key":"10132_CR57","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1016\/S0012-365X(03)00295-4","volume":"276","author":"J Vanherpe","year":"2004","unstructured":"Vanherpe, J.: Clique-width of partner-limited graphs. Discrete. Math. 276(1\u20133), 363\u2013374 (2004). https:\/\/doi.org\/10.1016\/S0012-365X(03)00295-4","journal-title":"Clique-width of partner-limited graphs. Discrete. Math."},{"issue":"1","key":"10132_CR58","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1016\/j.dam.2010.10.002","volume":"159","author":"CIB Velasquez","year":"2011","unstructured":"Velasquez, C.I.B., Bonomo, F., Koch, I.: On the b-coloring of $$P_4$$-tidy graphs. Discret. Appl. Math. 159(1), 60\u201368 (2011)","journal-title":"Discret. Appl. Math."},{"key":"10132_CR59","doi-asserted-by":"crossref","unstructured":"Wanke, E.: $$k$$-NLC graphs and polynomial algorithms. Discret. Appl. Math. 54, 251\u2013266 (1994)","DOI":"10.1016\/0166-218X(94)90026-4"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-023-10132-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-023-10132-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-023-10132-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,23]],"date-time":"2024-08-23T21:17:54Z","timestamp":1724447874000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-023-10132-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,9,23]]},"references-count":59,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,8]]}},"alternative-id":["10132"],"URL":"https:\/\/doi.org\/10.1007\/s00224-023-10132-0","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2023,9,23]]},"assertion":[{"value":"26 May 2023","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 September 2023","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declaration"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflicts of interest"}}]}}