{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T19:09:33Z","timestamp":1742929773218,"version":"3.40.3"},"publisher-location":"Cham","reference-count":27,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031491894"},{"type":"electronic","value":"9783031491900"}],"license":[{"start":{"date-parts":[[2023,12,9]],"date-time":"2023-12-09T00:00:00Z","timestamp":1702080000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,12,9]],"date-time":"2023-12-09T00:00:00Z","timestamp":1702080000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024]]},"DOI":"10.1007\/978-3-031-49190-0_12","type":"book-chapter","created":{"date-parts":[[2023,12,8]],"date-time":"2023-12-08T09:02:36Z","timestamp":1702026156000},"page":"168-181","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["List 3-Coloring on\u00a0Comb-Convex and\u00a0Caterpillar-Convex Bipartite Graphs"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4545-5044","authenticated-orcid":false,"given":"Banu","family":"Baklan \u015een","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9271-2691","authenticated-orcid":false,"given":"\u00d6znur","family":"Ya\u015far Diner","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4470-5868","authenticated-orcid":false,"given":"Thomas","family":"Erlebach","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,12,9]]},"reference":[{"key":"12_CR1","doi-asserted-by":"publisher","unstructured":"Baklan \u015een, B., Diner, \u00d6.Y., Erlebach, T.: List 3-coloring on comb-convex and caterpillar-convex bipartite graphs. CoRR abs\/2305.10108 (2023). https:\/\/doi.org\/10.48550\/arXiv.2305.10108","DOI":"10.48550\/arXiv.2305.10108"},{"key":"12_CR2","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.: Graph classes with structured neighborhoods and algorithmic applications. Theor. Comput. Sci. 511, 54\u201365 (2013). https:\/\/doi.org\/10.1016\/j.tcs.2013.01.011","journal-title":"Theor. Comput. Sci."},{"issue":"1\u20133","key":"12_CR3","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.: Precoloring extension. I. Interval graphs. Discret. Math. 100(1\u20133), 267\u2013279 (1992). https:\/\/doi.org\/10.1016\/0012-365X(92)90646-W","journal-title":"I. Interval graphs. Discret. Math."},{"issue":"4","key":"12_CR4","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.: Three-coloring and list three-coloring of graphs without induced paths on seven vertices. Comb. 38(4), 779\u2013801 (2018). https:\/\/doi.org\/10.1007\/s00493-017-3553-8","journal-title":"Comb."},{"key":"12_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1007\/978-3-030-83508-8_15","volume-title":"Algorithms and Data Structures","author":"F Bonomo-Braberman","year":"2021","unstructured":"Bonomo-Braberman, F., Brettell, N., Munaro, A., Paulusma, D.: Solving problems on generalized convex graphs via Mim-width. In: Lubiw, A., Salavatipour, M. (eds.) WADS 2021. LNCS, vol. 12808, pp. 200\u2013214. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-83508-8_15"},{"key":"12_CR6","unstructured":"Bonomo-Braberman, F., Brettell, N., Munaro, A., Paulusma, D.: Solving problems on generalized convex graphs via mim-width. CoRR abs\/2008.09004, September 2022. https:\/\/arxiv.org\/abs\/2008.09004"},{"key":"12_CR7","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.: List $$k$$-colouring $$P_t$$-free graphs: a mim-width perspective. Inf. Process. Lett. 173, 106168 (2022). https:\/\/doi.org\/10.1016\/j.ipl.2021.106168","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"12_CR8","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, F.V., Golovach, P.A., Paulusma, D.: Three complexity results on coloring $$P_k$$-free graphs. Eur. J. Comb. 34(3), 609\u2013619 (2013). https:\/\/doi.org\/10.1016\/j.ejc.2011.12.008","journal-title":"Eur. J. Comb."},{"issue":"4","key":"12_CR9","doi-asserted-by":"publisher","first-page":"533","DOI":"10.7155\/jgaa.00237","volume":"15","author":"K Buchin","year":"2011","unstructured":"Buchin, K., van Kreveld, M.J., Meijer, H., Speckmann, B., Verbeek, K.: On planar supports for hypergraphs. J. Graph Algorithms Appl. 15(4), 533\u2013549 (2011). https:\/\/doi.org\/10.7155\/jgaa.00237","journal-title":"J. Graph Algorithms Appl."},{"issue":"1","key":"12_CR10","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.: Complexity of domination, hamiltonicity and treewidth for tree convex bipartite graphs. J. Comb. Optim. 32(1), 95\u2013110 (2016). https:\/\/doi.org\/10.1007\/s10878-015-9917-3","journal-title":"J. Comb. Optim."},{"issue":"11","key":"12_CR11","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.: List $$3$$-coloring $$P_t$$-free graphs with no induced $$1$$-subdivision of $$K_{1, s}$$. Discret. Math. 343(11), 112086 (2020). https:\/\/doi.org\/10.1016\/j.disc.2020.112086","journal-title":"Discret. Math."},{"issue":"1","key":"12_CR12","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1007\/s00453-013-9777-0","volume":"71","author":"JF Couturier","year":"2015","unstructured":"Couturier, J.F., Golovach, P.A., Kratsch, D., Paulusma, D.: List coloring in the absence of a linear forest. Algorithmica 71(1), 21\u201335 (2015). https:\/\/doi.org\/10.1007\/s00453-013-9777-0","journal-title":"Algorithmica"},{"key":"12_CR13","first-page":"15","volume":"5","author":"J D\u00edaz","year":"2021","unstructured":"D\u00edaz, J., Diner, \u00d6., Serna, M., Serra, O.: On list $$k$$-coloring convex bipartite graphs. Graphs Comb. Optim. Theory Appl. 5, 15\u201326 (2021)","journal-title":"Graphs Comb. Optim. Theory Appl."},{"key":"12_CR14","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.: The complexity of colouring problems on dense graphs. Theor. Comput. Sci. 43, 337\u2013343 (1986). https:\/\/doi.org\/10.1016\/0304-3975(86)90184-2","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"12_CR15","doi-asserted-by":"publisher","first-page":"1675","DOI":"10.1137\/13090465X","volume":"28","author":"JA Enright","year":"2014","unstructured":"Enright, J.A., Stewart, L., Tardos, G.: On list coloring and list homomorphism of permutation and interval graphs. SIAM J. Discret. Math. 28(4), 1675\u20131685 (2014). https:\/\/doi.org\/10.1137\/13090465X","journal-title":"SIAM J. Discret. Math."},{"key":"12_CR16","unstructured":"Erd\u0151s, P., Rubin, A.L., Taylor, H.: Choosability in graphs. In: Proceedings of the West Coast Conference on Combinatorics, Graph Theory and Computing. Congressus Numerantium, vol. 26, pp. 125\u2013157 (1979)"},{"key":"12_CR17","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/j.dam.2013.10.010","volume":"166","author":"PA Golovach","year":"2014","unstructured":"Golovach, P.A., Paulusma, D.: List coloring in the absence of two subgraphs. Discret. Appl. Math. 166, 123\u2013130 (2014). https:\/\/doi.org\/10.1016\/j.dam.2013.10.010","journal-title":"Discret. Appl. Math."},{"issue":"1\u20133","key":"12_CR18","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.: Complexity of list coloring problems with a fixed total number of colors. Discret. Appl. Math. 117(1\u20133), 65\u201379 (2002). https:\/\/doi.org\/10.1016\/S0166-218X(01)00179-2","journal-title":"Discret. Appl. Math."},{"issue":"1","key":"12_CR19","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, C.T., Kaminski, M., Lozin, V.V., Sawada, J., Shu, X.: Deciding $$k$$-colorability of $$P_5$$-free graphs in polynomial time. Algorithmica 57(1), 74\u201381 (2010). https:\/\/doi.org\/10.1007\/s00453-008-9197-8","journal-title":"Algorithmica"},{"issue":"1","key":"12_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/jagm.2001.1205","volume":"43","author":"WL Hsu","year":"2002","unstructured":"Hsu, W.L.: A simple test for the consecutive ones property. J. Algorithms 43(1), 1\u201316 (2002). https:\/\/doi.org\/10.1006\/jagm.2001.1205","journal-title":"J. Algorithms"},{"issue":"11","key":"12_CR21","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.: Narrowing the complexity gap for coloring $$(C_s, P_t)$$-free graphs. Comput. J. 58(11), 3074\u20133088 (2015)","journal-title":"Comput. J."},{"issue":"2","key":"12_CR22","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.: Generalized coloring for tree-like graphs. Discret. Appl. Math. 75(2), 135\u2013155 (1997). https:\/\/doi.org\/10.1016\/S0166-218X(96)00085-6","journal-title":"Discret. Appl. Math."},{"key":"12_CR23","first-page":"139","volume":"62","author":"J Kratochvil","year":"1993","unstructured":"Kratochvil, J.: Precoloring extension with fixed color bound. Acta Math. Univ. Comen. 62, 139\u2013153 (1993)","journal-title":"Acta Math. Univ. Comen."},{"issue":"3","key":"12_CR24","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.: Algorithmic complexity of list colorings. Discret. Appl. Math. 50(3), 297\u2013302 (1994). https:\/\/doi.org\/10.1016\/0166-218X(94)90150-3","journal-title":"Discret. Appl. Math."},{"issue":"1","key":"12_CR25","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.: Some results concerning the complexity of restricted colorings of graphs. Discret. Appl. Math. 36(1), 35\u201346 (1992). https:\/\/doi.org\/10.1016\/0166-218X(92)90202-L","journal-title":"Discret. Appl. Math."},{"key":"12_CR26","unstructured":"Lov\u00e1sz, L.: Coverings and coloring of hypergraphs. In: Proceedings of the 4th Southeastern Confeernce on Combinatorics, Graph Theory, and Computing, Utilitas Math, pp. 3\u201312 (1973)"},{"issue":"29","key":"12_CR27","first-page":"3","volume":"101","author":"V Vizing","year":"1976","unstructured":"Vizing, V.: Coloring the vertices of a graph in prescribed colors. Diskret. Analiz 101(29), 3\u201310 (1976)","journal-title":"Diskret. Analiz"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-49190-0_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,12,8]],"date-time":"2023-12-08T09:09:35Z","timestamp":1702026575000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-49190-0_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,9]]},"ISBN":["9783031491894","9783031491900"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-49190-0_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2023,12,9]]},"assertion":[{"value":"9 December 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"COCOON","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Computing and Combinatorics Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Hawaii, HI","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15 December 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 December 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cocoon2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/theory.utdallas.edu\/COCOON2023\/org.html","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Double-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Springer EquinOCS","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"146","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"60","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"41% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"6","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"No","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}