{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,16]],"date-time":"2026-05-16T15:14:06Z","timestamp":1778944446472,"version":"3.51.4"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2026,5,16]],"date-time":"2026-05-16T00:00:00Z","timestamp":1778889600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,5,16]],"date-time":"2026-05-16T00:00:00Z","timestamp":1778889600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/S033483\/2"],"award-info":[{"award-number":["EP\/S033483\/2"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/T01461X\/1"],"award-info":[{"award-number":["EP\/T01461X\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2026,7]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    Given a graph\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$G=(V, E)$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>G<\/mml:mi>\n                            <mml:mo>=<\/mml:mo>\n                            <mml:mo>(<\/mml:mo>\n                            <mml:mi>V<\/mml:mi>\n                            <mml:mo>,<\/mml:mo>\n                            <mml:mi>E<\/mml:mi>\n                            <mml:mo>)<\/mml:mo>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    and a list of available colors\n                    <jats:italic>L<\/jats:italic>\n                    (\n                    <jats:italic>v<\/jats:italic>\n                    ) for each vertex\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$v\\in V$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>v<\/mml:mi>\n                            <mml:mo>\u2208<\/mml:mo>\n                            <mml:mi>V<\/mml:mi>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    , where\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$L(v) \\subseteq \\{1, 2, \\ldots , k\\}$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>L<\/mml:mi>\n                            <mml:mo>(<\/mml:mo>\n                            <mml:mi>v<\/mml:mi>\n                            <mml:mo>)<\/mml:mo>\n                            <mml:mo>\u2286<\/mml:mo>\n                            <mml:mo>{<\/mml:mo>\n                            <mml:mn>1<\/mml:mn>\n                            <mml:mo>,<\/mml:mo>\n                            <mml:mn>2<\/mml:mn>\n                            <mml:mo>,<\/mml:mo>\n                            <mml:mo>\u2026<\/mml:mo>\n                            <mml:mo>,<\/mml:mo>\n                            <mml:mi>k<\/mml:mi>\n                            <mml:mo>}<\/mml:mo>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    ,\n                    <jats:sc>List<\/jats:sc>\n                    <jats:italic>k<\/jats:italic>\n                    -\n                    <jats:sc>Coloring<\/jats:sc>\n                    refers to the problem of assigning colors to the vertices of\n                    <jats:italic>G<\/jats:italic>\n                    such that each vertex receives a color from its own list and no two neighboring vertices receive the same color. The decision version of the problem\n                    <jats:sc>List<\/jats:sc>\n                    3-\n                    <jats:sc>Coloring<\/jats:sc>\n                    is NP-complete even for bipartite graphs, and its complexity on comb-convex bipartite graphs has been an open problem. We give a polynomial-time algorithm to solve\n                    <jats:sc>List<\/jats:sc>\n                    3-\n                    <jats:sc>Coloring<\/jats:sc>\n                    for caterpillar-convex bipartite graphs, a superclass of comb-convex bipartite graphs. We also give a polynomial-time recognition algorithm for the class of caterpillar-convex bipartite graphs.\n                  <\/jats:p>","DOI":"10.1007\/s10878-026-01424-5","type":"journal-article","created":{"date-parts":[[2026,5,16]],"date-time":"2026-05-16T14:48:42Z","timestamp":1778942922000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["List 3-coloring on comb-convex and caterpillar-convex bipartite graphs"],"prefix":"10.1007","volume":"51","author":[{"given":"Banu Baklan","family":"\u015een","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4470-5868","authenticated-orcid":false,"given":"Thomas","family":"Erlebach","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"\u00d6znur","family":"Ya\u015far","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2026,5,16]]},"reference":[{"key":"1424_CR1","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1016\/j.tcs.2013.01.011","volume":"511","author":"R Belmonte","year":"2013","unstructured":"Belmonte R, Vatshelle M (2013) Graph classes with structured neighborhoods and algorithmic applications. Theor Comput Sci 511:54\u201365. https:\/\/doi.org\/10.1016\/j.tcs.2013.01.011","journal-title":"Theor Comput Sci"},{"issue":"1\u20133","key":"1424_CR2","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1016\/0012-365X(92)90646-W","volume":"100","author":"M Bir\u00f3","year":"1992","unstructured":"Bir\u00f3 M, Hujter M, Tuza Z (1992) Precoloring extension. I Interval graphs Discret Math 100(1\u20133):267\u2013279. https:\/\/doi.org\/10.1016\/0012-365X(92)90646-W","journal-title":"I Interval graphs Discret Math"},{"issue":"4","key":"1424_CR3","doi-asserted-by":"publisher","first-page":"779","DOI":"10.1007\/s00493-017-3553-8","volume":"38","author":"F Bonomo","year":"2018","unstructured":"Bonomo F, Chudnovsky M, Maceli P, Schaudt O, Stein M, Zhong M (2018) Three-coloring and list three-coloring of graphs without induced paths on seven vertices. Comb 38(4):779\u2013801. https:\/\/doi.org\/10.1007\/s00493-017-3553-8","journal-title":"Comb"},{"key":"1424_CR4","doi-asserted-by":"publisher","unstructured":"Bonomo-Braberman F, Brettell N, Munaro A, Paulusma D (2021) Solving problems on generalized convex graphs via mim-width. In: WADS 2021, Springer, Lecture Notes in Computer Science, vol 12808, pp 200\u2013214 https:\/\/doi.org\/10.1007\/978-3-030-83508-8_15","DOI":"10.1007\/978-3-030-83508-8_15"},{"key":"1424_CR5","doi-asserted-by":"publisher","DOI":"10.1016\/J.JCSS.2023.103493","volume":"140","author":"F Bonomo-Braberman","year":"2024","unstructured":"Bonomo-Braberman F, Brettell N, Munaro A, Paulusma D (2024) Solving problems on generalized convex graphs via mim-width. J Comput Syst Sci 140:103493. https:\/\/doi.org\/10.1016\/J.JCSS.2023.103493","journal-title":"J Comput Syst Sci"},{"key":"1424_CR6","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2021.106168","volume":"173","author":"N Brettell","year":"2022","unstructured":"Brettell N, Horsfield J, Munaro A, Paulusma D (2022) List $$k$$-colouring $$P_t$$-free graphs: a mim-width perspective. Inf Process Lett 173:106168. https:\/\/doi.org\/10.1016\/j.ipl.2021.106168","journal-title":"Inf Process Lett"},{"issue":"3","key":"1424_CR7","doi-asserted-by":"publisher","first-page":"609","DOI":"10.1016\/j.ejc.2011.12.008","volume":"34","author":"H Broersma","year":"2013","unstructured":"Broersma H, Fomin FV, Golovach PA, Paulusma D (2013) Three complexity results on coloring $$P_k$$-free graphs. Eur J Comb 34(3):609\u2013619. https:\/\/doi.org\/10.1016\/j.ejc.2011.12.008","journal-title":"Eur J Comb"},{"issue":"4","key":"1424_CR8","doi-asserted-by":"publisher","first-page":"533","DOI":"10.7155\/jgaa.00237","volume":"15","author":"K Buchin","year":"2011","unstructured":"Buchin K, van Kreveld MJ, Meijer H, Speckmann B, Verbeek K (2011) On planar supports for hypergraphs. J Graph Algorithms Appl 15(4):533\u2013549. https:\/\/doi.org\/10.7155\/jgaa.00237","journal-title":"J Graph Algorithms Appl"},{"issue":"1","key":"1424_CR9","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1007\/s10878-015-9917-3","volume":"32","author":"H Chen","year":"2016","unstructured":"Chen H, Lei Z, Liu T, Tang Z, Wang C, Xu K (2016) Complexity of domination, hamiltonicity and treewidth for tree convex bipartite graphs. J Comb Optim 32(1):95\u2013110. https:\/\/doi.org\/10.1007\/s10878-015-9917-3","journal-title":"J Comb Optim"},{"issue":"11","key":"1424_CR10","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2020.112086","volume":"343","author":"M Chudnovsky","year":"2020","unstructured":"Chudnovsky M, Spirkl S, Zhong M (2020) List $$3$$-coloring $$P_t$$-free graphs with no induced $$1$$-subdivision of $$K_{1, s}$$. Discret Math 343(11):112086. https:\/\/doi.org\/10.1016\/j.disc.2020.112086","journal-title":"Discret Math"},{"issue":"1","key":"1424_CR11","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1007\/s00453-013-9777-0","volume":"71","author":"JF Couturier","year":"2015","unstructured":"Couturier JF, Golovach PA, Kratsch D, Paulusma D (2015) List coloring in the absence of a linear forest. Algorithmica 71(1):21\u201335. https:\/\/doi.org\/10.1007\/s00453-013-9777-0","journal-title":"Algorithmica"},{"key":"1424_CR12","first-page":"15","volume":"5","author":"J D\u00edaz","year":"2021","unstructured":"D\u00edaz J, Diner \u00d6, Serna M, Serra O (2021) On list $$k$$-coloring convex bipartite graphs. Graphs and Comb Opt from Theory to Appl 5:15\u201326","journal-title":"Graphs and Comb Opt from Theory to Appl"},{"key":"1424_CR13","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1016\/0304-3975(86)90184-2","volume":"43","author":"K Edwards","year":"1986","unstructured":"Edwards K (1986) The complexity of colouring problems on dense graphs. Theor Comput Sci 43:337\u2013343. https:\/\/doi.org\/10.1016\/0304-3975(86)90184-2","journal-title":"Theor Comput Sci"},{"issue":"4","key":"1424_CR14","doi-asserted-by":"publisher","first-page":"1675","DOI":"10.1137\/13090465X","volume":"28","author":"JA Enright","year":"2014","unstructured":"Enright JA, Stewart L, Tardos G (2014) On list coloring and list homomorphism of permutation and interval graphs. SIAM J Discret Math 28(4):1675\u20131685. https:\/\/doi.org\/10.1137\/13090465X","journal-title":"SIAM J Discret Math"},{"key":"1424_CR15","first-page":"125","volume":"26","author":"P Erd\u0151s","year":"1979","unstructured":"Erd\u0151s P, Rubin AL, Taylor H (1979) Choosability in graphs. Proc of the West Coast Conf on Comb Graph Theory and Comput Congressus Numerantium 26:125\u2013157","journal-title":"Proc of the West Coast Conf on Comb Graph Theory and Comput Congressus Numerantium"},{"key":"1424_CR16","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/j.dam.2013.10.010","volume":"166","author":"PA Golovach","year":"2014","unstructured":"Golovach PA, Paulusma D (2014) List coloring in the absence of two subgraphs. Discret Appl Math 166:123\u2013130. https:\/\/doi.org\/10.1016\/j.dam.2013.10.010","journal-title":"Discret Appl Math"},{"issue":"1\u20133","key":"1424_CR17","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1016\/S0166-218X(01)00179-2","volume":"117","author":"S Gravier","year":"2002","unstructured":"Gravier S, Kobler D, Kubiak W (2002) Complexity of list coloring problems with a fixed total number of colors. Discret Appl Math 117(1\u20133):65\u201379. https:\/\/doi.org\/10.1016\/S0166-218X(01)00179-2","journal-title":"Discret Appl Math"},{"issue":"1","key":"1424_CR18","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1007\/s00453-008-9197-8","volume":"57","author":"CT Ho\u00e0ng","year":"2010","unstructured":"Ho\u00e0ng CT, Kaminski M, Lozin VV, Sawada J, Shu X (2010) Deciding $$k$$-colorability of $$P_5$$-free graphs in polynomial time. Algorithmica 57(1):74\u201381. https:\/\/doi.org\/10.1007\/s00453-008-9197-8","journal-title":"Algorithmica"},{"issue":"1","key":"1424_CR19","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/jagm.2001.1205","volume":"43","author":"WL Hsu","year":"2002","unstructured":"Hsu WL (2002) A simple test for the consecutive ones property. J Algorithms 43(1):1\u201316. https:\/\/doi.org\/10.1006\/jagm.2001.1205","journal-title":"J Algorithms"},{"issue":"11","key":"1424_CR20","doi-asserted-by":"publisher","first-page":"3074","DOI":"10.1093\/comjnl\/bxv039","volume":"58","author":"S Huang","year":"2015","unstructured":"Huang S, Johnson M, Paulusma D (2015) Narrowing the complexity gap for coloring $$(C_s, P_t)$$-free graphs. Comput J 58(11):3074\u20133088","journal-title":"Comput J"},{"issue":"2","key":"1424_CR21","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/S0166-218X(96)00085-6","volume":"75","author":"K Jansen","year":"1997","unstructured":"Jansen K, Scheffler P (1997) Generalized coloring for tree-like graphs. Discret Appl Math 75(2):135\u2013155. https:\/\/doi.org\/10.1016\/S0166-218X(96)00085-6","journal-title":"Discret Appl Math"},{"key":"1424_CR22","first-page":"139","volume":"62","author":"J Kratochvil","year":"1993","unstructured":"Kratochvil J (1993) Precoloring extension with fixed color bound. Acta Math Univ Comen 62:139\u2013153","journal-title":"Acta Math Univ Comen"},{"issue":"3","key":"1424_CR23","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1016\/0166-218X(94)90150-3","volume":"50","author":"J Kratochv\u00edl","year":"1994","unstructured":"Kratochv\u00edl J, Tuza Z (1994) Algorithmic complexity of list colorings. Discret Appl Math 50(3):297\u2013302. https:\/\/doi.org\/10.1016\/0166-218X(94)90150-3","journal-title":"Discret Appl Math"},{"issue":"1","key":"1424_CR24","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/0166-218X(92)90202-L","volume":"36","author":"M Kubale","year":"1992","unstructured":"Kubale M (1992) Some results concerning the complexity of restricted colorings of graphs. Discret Appl Math 36(1):35\u201346. https:\/\/doi.org\/10.1016\/0166-218X(92)90202-L","journal-title":"Discret Appl Math"},{"key":"1424_CR25","unstructured":"Lov\u00e1sz L (1973) Coverings and coloring of hypergraphs. In: Proc 4th Southeastern Conf on Combinatorics, Graph Theory, and Computing, Utilitas Math, pp 3\u201312"},{"issue":"29","key":"1424_CR26","first-page":"3","volume":"101","author":"V Vizing","year":"1976","unstructured":"Vizing V (1976) Coloring the vertices of a graph in prescribed colors. Diskret Analiz 101(29):3\u201310","journal-title":"Diskret Analiz"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-026-01424-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-026-01424-5","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-026-01424-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,16]],"date-time":"2026-05-16T14:48:45Z","timestamp":1778942925000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-026-01424-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5,16]]},"references-count":26,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2026,7]]}},"alternative-id":["1424"],"URL":"https:\/\/doi.org\/10.1007\/s10878-026-01424-5","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5,16]]},"assertion":[{"value":"2 June 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 May 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 May 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing Interests"}}],"article-number":"47"}}