{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T09:39:16Z","timestamp":1776764356673,"version":"3.51.2"},"reference-count":47,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2026,2,24]],"date-time":"2026-02-24T00:00:00Z","timestamp":1771891200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,2,24]],"date-time":"2026-02-24T00:00:00Z","timestamp":1771891200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003945","name":"Link\u00f6ping University","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100003945","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2026,3]]},"abstract":"Abstract<\/jats:title>\n \n The\n \n H<\/jats:italic>\n <\/jats:bold>\n -\n Coloring<\/jats:sc>\n problem is a well-known generalization of the classical -complete problem\n \n k<\/jats:italic>\n <\/jats:bold>\n -\n Coloring<\/jats:sc>\n where the task is to determine whether an input graph admits a homomorphism to the template graph\n \n H<\/jats:italic>\n <\/jats:bold>\n . This problem has been the subject of intense theoretical research and in this article we study the complexity of\n \n H<\/jats:italic>\n <\/jats:bold>\n -\n Coloring<\/jats:sc>\n with respect to the parameters\n clique-width<\/jats:italic>\n and the more recent\n component twin-width<\/jats:italic>\n , which describe desirable computational properties of graphs. We give two surprising linear bounds between these parameters, thus improving the previously known exponential and double exponential bounds. Our constructive proof naturally extends to related parameters and as a showcase we prove that\n total twin-width<\/jats:italic>\n and\n linear clique-width<\/jats:italic>\n can be related via a tight quadratic bound. These bounds naturally lead to algorithmic applications. The linear bounds between component twin-width and clique-width entail natural approximations of component twin-width, by making use of the results known for clique-width. As for computational aspects of graph coloring, we target the richer problem of counting the number of homomorphisms to\n \n H<\/jats:italic>\n <\/jats:bold>\n (#\n \n H<\/jats:italic>\n <\/jats:bold>\n -\n Coloring<\/jats:sc>\n ). The first algorithm that we propose uses a contraction sequence of the input graph\n \n G<\/jats:italic>\n <\/jats:bold>\n parameterized by the component twin-width of\n \n G<\/jats:italic>\n <\/jats:bold>\n . This leads to a positive result for the counting version. The second uses a contraction sequence of the template graph\n \n H<\/jats:italic>\n <\/jats:bold>\n and here we instead measure the complexity with respect to the number of vertices in the input graph. Using our linear bounds we show that our algorithms are\n always<\/jats:italic>\n at least as fast as the previously best #\n \n H<\/jats:italic>\n <\/jats:bold>\n -Coloring algorithms (based on clique-width) and for several interesting classes of graphs (e.g., cographs, cycles of length\n \n \n $$\\varvec{\\ge 7}$$<\/jats:tex-math>\n \n \n \u2265<\/mml:mo>\n 7<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , or distance-hereditary graphs) are in fact strictly faster.\n <\/jats:p>","DOI":"10.1007\/s00224-025-10233-y","type":"journal-article","created":{"date-parts":[[2026,2,24]],"date-time":"2026-02-24T12:23:10Z","timestamp":1771935790000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Improved Bounds for Twin-Width Parameter Variants with Algorithmic Applications to Counting Graph Colorings"],"prefix":"10.1007","volume":"70","author":[{"given":"Ambroise","family":"Baril","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Miguel","family":"Couceiro","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Victor","family":"Lagerkvist","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2026,2,24]]},"reference":[{"issue":"3","key":"10233_CR1","doi-asserted-by":"publisher","first-page":"223","DOI":"10.2478\/v10209-011-0012-y","volume":"37","author":"P Formanowicz","year":"2012","unstructured":"Formanowicz, P., Tana\u015b, K.: A survey of graph coloring-its types, methods and applications. Found. Comput. Decision Sci. 37(3), 223\u2013238 (2012)","journal-title":"Found. Comput. Decision Sci."},{"issue":"3\u20134","key":"10233_CR2","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1002\/1098-2418(200010\/12)17:3\/4<260::AID-RSA5>3.0.CO;2-W","volume":"17","author":"M Dyer","year":"2000","unstructured":"Dyer, M., Greenhill, C.: The complexity of counting graph homomorphisms. Random Struct. Algorithms 17(3\u20134), 260\u2013289 (2000)","journal-title":"Random Struct. Algorithms"},{"key":"10233_CR3","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-16533-7","volume-title":"Exact Exponential Algorithms","author":"FV Fomin","year":"2010","unstructured":"Fomin, F.V., Kratsch, D.: Exact Exponential Algorithms. Texts in Theoretical Computer Science. An EATCS Series. Springer, Berlin, Heidelberg (2010)"},{"key":"10233_CR4","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Golovnev, A., Kulikov, A.S., Mihajlin, I.: Lower bounds for the graph homomorphism problem. In: Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP-2015). Lecture Notes in Computer Science, vol. 9134, pp. 481\u2013493 (2015)","DOI":"10.1007\/978-3-662-47672-7_39"},{"key":"10233_CR5","unstructured":"Ganian, R., Hamm, T., Korchemna, V., Okrasa, K., Simonov, K.: The fine-grained complexity of graph homomorphism parameterized by clique-width. In: Bojanczyk, M., Merelli, E., Woodruff, D.P. (eds.) Proceedings of the 49th International Colloquium on Automata, Languages, and Programming (ICALP-2022). LIPIcs, vol. 229, pp. 66\u201316620 (2022)"},{"issue":"2","key":"10233_CR6","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1007\/s00224-010-9261-z","volume":"49","author":"M Wahlstr\u00f6m","year":"2011","unstructured":"Wahlstr\u00f6m, M.: New plain-exponential time classes for graph homomorphism. Theory Comput. Syst. 49(2), 273\u2013282 (2011)","journal-title":"Theory Comput. Syst."},{"key":"10233_CR7","unstructured":"Bulatov, A.A., Dadsetan, A.: Counting homomorphisms in plain exponential time. In: Czumaj, A., Dawar, A., Merelli, E. (eds.) Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP-2020). LIPIcs, vol. 168, pp. 21\u201312118 (2020)"},{"key":"10233_CR8","unstructured":"Berg\u00e9, P., Bonnet, \u00c9., D\u00e9pr\u00e9s, H.: Deciding twin-width at most 4 is NP-complete. In: Bojanczyk, M., Merelli, E., Woodruff, D.P. (eds.) Proceedings of the 49th International Colloquium on Automata, Languages, and Programming (ICALP-2022). LIPIcs, vol. 229, pp. 18\u201311820 (2022)"},{"key":"10233_CR9","unstructured":"Bonnet, \u00c9., Chakraborty, D., Kim, E.J., K\u00f6hler, N., Lopes, R., Thomass\u00e9, S.: Twin-Width VIII: Delineation and Win-Wins. In: Dell, H., Nederlof, J. (eds.) Proceedings of the 17th International Symposium on Parameterized and Exact Computation (IPEC-2022). Leibniz International Proceedings in Informatics (LIPIcs), vol. 249, pp. 9\u20131918 (2022)"},{"key":"10233_CR10","doi-asserted-by":"crossref","unstructured":"Bonnet, \u00c9., D\u00e9pr\u00e9s, H.: Twin-width can be exponential in treewidth. J. Combinatorial Theory, Series B 161, 1\u201314 (2023)","DOI":"10.1016\/j.jctb.2023.01.003"},{"key":"10233_CR11","unstructured":"Bonnet, \u00c9., Geniet, C., Kim, E.J., Thomass\u00e9, S., Watrigant, R.: Twin-width III: Max Independent Set, Min Dominating Set, and Coloring. In: Proceedings of the 48th International Colloquium on Automata, Languages, and Programming (ICALP-2021). Leibniz International Proceedings in Informatics (LIPIcs), vol. 198, pp. 35\u201313520 (2021)"},{"key":"10233_CR12","doi-asserted-by":"crossref","unstructured":"Bonnet, \u00c9., Geniet, C., Kim, E.J., Thomass\u00e9, S., Watrigant, R.: Twin-width II: small classes. In: Proceedings of the 32nd ACM-SIAM Symposium on Discrete Algorithms (SODA-2021), pp. 1977\u20131996 (2021)","DOI":"10.1137\/1.9781611976465.118"},{"key":"10233_CR13","unstructured":"Bonnet, \u00c9., Geniet, C., Tessera, R., Thomass\u00e9, S.: Twin-width VII: groups (2022). arXiv:"},{"key":"10233_CR14","doi-asserted-by":"crossref","unstructured":"Bonnet, \u00c9., Giocanti, U., Mendez, P., Simon, P., Thomass\u00e9, S., Toru\u0144czyk, S.: Twin-width IV: ordered graphs and matrices. In: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC-2022), pp. 924\u2013937 (2022)","DOI":"10.1145\/3519935.3520037"},{"key":"10233_CR15","doi-asserted-by":"crossref","unstructured":"Bonnet, \u00c9., Kim, E.J., Reinald, A., Thomass\u00e9, S.: Twin-width VI: the lens of contraction sequences. In: Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-2022), pp. 1036\u20131056 (2022)","DOI":"10.1137\/1.9781611977073.45"},{"key":"10233_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00453-022-00965-5","volume":"84","author":"\u00c9 Bonnet","year":"2022","unstructured":"Bonnet, \u00c9., Kim, E.J., Reinald, A., Thomass\u00e9, S., Watrigant, R.: Twin-width and polynomial kernels. Algorithmica 84, 1\u201338 (2022)","journal-title":"Algorithmica"},{"key":"10233_CR17","unstructured":"Bonnet, \u00c9., Kwon, O.-j., Wood, D.R., et\u00a0al.: Reduced bandwidth: a qualitative strengthening of twin-width in minor-closed classes (and beyond) (2022). arXiv:2202.11858"},{"key":"10233_CR18","unstructured":"Bonnet, \u00c9., Ne\u0161et\u0159il, J., Mendez, P.O., Siebertz, S., Thomass\u00e9, S.: Twin-width and permutations (2021). arXiv:2102.06880"},{"key":"10233_CR19","doi-asserted-by":"crossref","unstructured":"Schidler, A., Szeider, S.: A SAT approach to twin-width. In: Phillips, C.A., Speckmann, B. (eds.) Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX-2022), pp. 67\u201377 (2022)","DOI":"10.1137\/1.9781611977042.6"},{"key":"10233_CR20","unstructured":"Gajarsk\u00fd, J., Pilipczuk, M., Przybyszewski, W., Torunczyk, S.: Twin-width and types. In: Bojanczyk, M., Merelli, E., Woodruff, D.P. (eds.) Proceedings of the 49th International Colloquium on Automata, Languages, and Programming (ICALP-2022). LIPIcs, vol. 229, pp. 123\u2013112321 (2022)"},{"issue":"3","key":"10233_CR21","doi-asserted-by":"publisher","first-page":"2352","DOI":"10.1137\/21M1452834","volume":"36","author":"J Ahn","year":"2022","unstructured":"Ahn, J., Hendrey, K., Kim, D., Oum, S.: Bounds for the twin-width of graphs. SIAM J. Discrete Math. 36(3), 2352\u20132366 (2022)","journal-title":"SIAM J. Discrete Math."},{"issue":"3","key":"10233_CR22","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2021.112746","volume":"345","author":"J Dreier","year":"2022","unstructured":"Dreier, J., Gajarsk\u00fd, J., Jiang, Y., Mendez, P.O., Raymond, J.: Twin-width and generalized coloring numbers. Discrete Math. 345(3), 112746 (2022)","journal-title":"Discrete Math."},{"key":"10233_CR23","unstructured":"Balab\u00e1n, J., Hlin\u011bn\u00fd, P.: Twin-width is linear in the poset width (2021). arXiv:2106.15337"},{"key":"10233_CR24","doi-asserted-by":"crossref","unstructured":"Gajarsk\u00fd, J., Pilipczuk, M., Toru\u0144czyk, S.: Stable graphs of bounded twin-width. In: Proceedings of the 37th Annual ACM\/IEEE Symposium on Logic in Computer Science, pp. 1\u201312 (2022)","DOI":"10.1145\/3531130.3533356"},{"key":"10233_CR25","unstructured":"Ganian, R., Pokr\u00fdvka, F., Schidler, A., Simonov, K., Szeider, S.: Weighted model counting with twin-width (2022). arXiv:2206.01706"},{"key":"10233_CR26","unstructured":"Kr\u00e1l\u2019, D., Pek\u00e1rkov\u00e1, K., \u0160torgel, K.: Twin-width of graphs on surfaces (2023). arXiv:2307.05811"},{"key":"10233_CR27","unstructured":"Pilipczuk, M., Soko\u0142owski, M., Zych-Pawlewicz, A.: Compact representation for matrices of bounded twin-width (2021). arXiv:2110.08106"},{"key":"10233_CR28","doi-asserted-by":"crossref","unstructured":"Balab\u00e1n, J., Hlin\u011bn\u00fd, P., Jedelsk\u00fd, J.: Twin-width and transductions of proper k-mixed-thin graphs. Discrete Mathematics, 113876 (2024)","DOI":"10.1016\/j.disc.2024.113876"},{"key":"10233_CR29","doi-asserted-by":"crossref","unstructured":"Pilipczuk, M., Soko\u0142owski, M.: Graphs of bounded twin-width are quasi-polynomially $$\\chi $$-bounded. J. Combinatorial Theory, Series B 161, 382\u2013406 (2023)","DOI":"10.1016\/j.jctb.2023.02.006"},{"key":"10233_CR30","unstructured":"Hlin\u011bn\u00fd, P., Jedelsk\u00fd, J.: Twin-width of planar graphs is at most 8, and at most 6 when bipartite planar. In: Etessami, K., Feige, U., Puppis, G. (eds.) Proceedings of the 50th International Colloquium on Automata, Languages, and Programming (ICALP-2023). LIPIcs, vol. 261, pp. 75\u201317518 (2023)"},{"key":"10233_CR31","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1016\/j.jcss.2017.02.002","volume":"87","author":"R Haan","year":"2017","unstructured":"Haan, R., Szeider, S.: Parameterized complexity classes beyond para-NP. J. Comput. Syst. Sci. 87, 16\u201357 (2017)","journal-title":"J. Comput. Syst. Sci."},{"issue":"39","key":"10233_CR32","doi-asserted-by":"publisher","first-page":"5187","DOI":"10.1016\/j.tcs.2011.05.022","volume":"412","author":"B-M Bui-Xuan","year":"2011","unstructured":"Bui-Xuan, B.-M., Telle, J.A., Vatshelle, M.: Boolean-width of graphs. Theoretical Comput. Sci. 412(39), 5187\u20135204 (2011)","journal-title":"Boolean-width of graphs. Theoretical Comput. Sci."},{"key":"10233_CR33","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, 1st edn. Springer, Berlin, Heidelberg (2015)","edition":"1"},{"key":"10233_CR34","unstructured":"Bodlaender, H.L., Groenland, C., Jacob, H., Jaffke, L., Lima, P.T.: XNLP-completeness for parameterized problems on graphs with a linear structure. In: Dell, H., Nederlof, J. (eds.) Proceedings of the 17th International Symposium on Parameterized and Exact Computation (IPEC-2022). LIPIcs, vol. 249, pp. 8\u20131818 (2022)"},{"issue":"1","key":"10233_CR35","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1145\/3280824","volume":"15","author":"FV Fomin","year":"2019","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\u20131927 (2019)","journal-title":"ACM Trans. Algorithms"},{"issue":"03","key":"10233_CR36","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."},{"key":"10233_CR37","volume-title":"Parameterized Complexity Theory","author":"J Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, Berlin, Heidelberg (2006)"},{"issue":"1","key":"10233_CR38","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/0304-3975(93)90064-Z","volume":"109","author":"B Courcelle","year":"1993","unstructured":"Courcelle, B., Mosbah, M.: Monadic second-order evaluations on tree-decomposable graphs. Theoretical Comput. Sci. 109(1), 49\u201382 (1993)","journal-title":"Theoretical Comput. Sci."},{"issue":"4","key":"10233_CR39","doi-asserted-by":"publisher","first-page":"926","DOI":"10.1137\/0214065","volume":"14","author":"DG Corneil","year":"1985","unstructured":"Corneil, D.G., Perl, Y., Stewart, L.K.: A linear recognition algorithm for cographs. SIAM J. Comput. 14(4), 926\u2013934 (1985)","journal-title":"SIAM J. Comput."},{"issue":"1\u20133","key":"10233_CR40","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. Discrete Appl. Math. 101(1\u20133), 77\u2013114 (2000)","journal-title":"Discrete Appl. Math."},{"key":"10233_CR41","doi-asserted-by":"crossref","unstructured":"Bonnet, \u00c9., Kim, E.J., Thomass\u00e9, S., Watrigant, R.: Twin-width I: tractable FO model checking. In: Proceedings of the 61st Annual Symposium on Foundations of Computer Science (FOCS-2020), pp. 601\u2013612 (2020)","DOI":"10.1109\/FOCS46700.2020.00062"},{"key":"10233_CR42","unstructured":"Oum, S.-i.: Graphs of Bounded Rank-width. Princeton University, Princeton, New Jersey (2005)"},{"issue":"1\u20132","key":"10233_CR43","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1016\/j.tcs.2005.05.018","volume":"347","author":"F Gurski","year":"2005","unstructured":"Gurski, F., Wanke, E.: On the relationship between nlc-width and linear nlc-width. Theoretical Comput. Sci. 347(1\u20132), 76\u201389 (2005)","journal-title":"Theoretical Comput. Sci."},{"key":"10233_CR44","doi-asserted-by":"crossref","unstructured":"Jeong, J., Kim, E.J., Oum, S.-i.: Finding branch-decompositions of matroids, hypergraphs, and more. SIAM J. Discrete Math. 35(4), 2544\u20132617 (2021)","DOI":"10.1137\/19M1285895"},{"key":"10233_CR45","doi-asserted-by":"crossref","unstructured":"Oum, S.-i., Seymour, P.: Approximating clique-width and branch-width. J. Combinatorial Theory, Series B 96, 514\u2013528 (2006) 10.1016\/j.jctb.2005.10.006","DOI":"10.1016\/j.jctb.2005.10.006"},{"key":"10233_CR46","doi-asserted-by":"crossref","unstructured":"Jeong, J., Kim, E.J., Oum, S.-i.: The \u201cart of trellis decoding\u201d is fixed-parameter tractable. IEEE Trans. Inf. Theory 63(11), 7178\u20137205 (2017)","DOI":"10.1109\/TIT.2017.2740283"},{"key":"10233_CR47","doi-asserted-by":"crossref","unstructured":"Dabrowski, K.K., Jonsson, P., Ordyniak, S., Osipov, G.: Solving infinite-domain CSPs using the patchwork property. In: Proceedings of the Thirty-Fifth AAAI Conference on Artificial Intelligence (AAAI-2021), pp. 3715\u20133723 (2021)","DOI":"10.1609\/aaai.v35i5.16488"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-025-10233-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-025-10233-y","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-025-10233-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T08:42:37Z","timestamp":1776760957000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-025-10233-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,2,24]]},"references-count":47,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,3]]}},"alternative-id":["10233"],"URL":"https:\/\/doi.org\/10.1007\/s00224-025-10233-y","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,2,24]]},"assertion":[{"value":"24 July 2025","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 February 2026","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"12"}}