{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T01:56:55Z","timestamp":1743127015727,"version":"3.40.3"},"publisher-location":"Cham","reference-count":28,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783031206238"},{"type":"electronic","value":"9783031206245"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"DOI":"10.1007\/978-3-031-20624-5_36","type":"book-chapter","created":{"date-parts":[[2022,10,28]],"date-time":"2022-10-28T15:18:05Z","timestamp":1666970285000},"page":"593-609","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["List Homomorphism: Beyond the\u00a0Known Boundaries"],"prefix":"10.1007","author":[{"given":"Sriram","family":"Bhyravarapu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Satyabrata","family":"Jana","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fahad","family":"Panolan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shaily","family":"Verma","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,10,29]]},"reference":[{"key":"36_CR1","unstructured":"Bok, J., Brewster, R., Feder, T., Hell, P., Jedli\u010dkov\u00e1, N.: List homomorphism problems for signed graphs. arXiv preprint arXiv:2005.05547 (2020)"},{"key":"36_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1007\/978-3-030-95018-7_3","volume-title":"Algorithms and Discrete Applied Mathematics","author":"J Bok","year":"2022","unstructured":"Bok, J., Brewster, R., Feder, T., Hell, P., Jedli\u010dkov\u00e1, N.: List homomorphisms to\u00a0separable signed graphs. In: Balachandran, N., Inkulu, R. (eds.) CALDAM 2022. LNCS, vol. 13179, pp. 22\u201335. Springer, Cham (2022). https:\/\/doi.org\/10.1007\/978-3-030-95018-7_3"},{"key":"36_CR3","unstructured":"Brandst\u00e4dt, A., Lozin, V.V.: On the linear structure and clique-width of bipartite permutation graphs. Ars Comb. 67 (2003)"},{"key":"36_CR4","unstructured":"Chen, H., Jansen, B.M.P., Okrasa, K., Pieterse, A., Rzazewski, P.: Sparsification lower bounds for list $$H$$-coloring. In: Cao, Y., Cheng, S.-W., Li, M. (eds.) 31st International Symposium on Algorithms and Computation, ISAAC 2020, 14\u201318 December 2020. LIPIcs, vol. 181, pp. 58:1\u201358:17 (2020)"},{"issue":"1","key":"36_CR5","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1007\/s00453-016-0139-6","volume":"78","author":"R Chitnis","year":"2017","unstructured":"Chitnis, R., Egri, L., Marx, D.: List $$h$$-coloring a graph by removing few vertices. Algorithmica 78(1), 110\u2013146 (2017)","journal-title":"Algorithmica"},{"key":"36_CR6","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., et al.: Parameterized Algorithms, vol. 5. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-21275-3"},{"key":"36_CR7","series-title":"AIRO Springer Series","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1007\/978-3-030-63072-0_2","volume-title":"Graphs and Combinatorial Optimization: from Theory to Applications","author":"J D\u00edaz","year":"2021","unstructured":"D\u00edaz, J., Diner, \u00d6.Y., Serna, M., Serra, O.: On list k-coloring convex bipartite graphs. In: Gentile, C., Stecca, G., Ventura, P. (eds.) Graphs and Combinatorial Optimization: from Theory to Applications. ASS, vol. 5, pp. 15\u201326. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-63072-0_2"},{"issue":"1\u20132","key":"36_CR8","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1016\/S0304-3975(02)00017-8","volume":"281","author":"J D\u00edaz","year":"2002","unstructured":"D\u00edaz, J., Serna, M.J., Thilikos, D.M.: Counting h-colorings of partial k-trees. Theor. Comput. Sci. 281(1\u20132), 291\u2013309 (2002)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"36_CR9","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1007\/s00224-011-9333-8","volume":"51","author":"L Egri","year":"2012","unstructured":"Egri, L., Krokhin, A., Larose, B., Tesson, P.: The complexity of the list homomorphism problem for graphs. Theory Comput. Syst. 51(2), 143\u2013178 (2012)","journal-title":"Theory Comput. Syst."},{"issue":"4","key":"36_CR10","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)","journal-title":"SIAM J. Discret. Math."},{"key":"36_CR11","unstructured":"Erd\u00f6s, P., Rubin, A.L., Taylor, H.: Choosability in graphs. In: Proceedings West Coast Conference on Combinatorics, Graph Theory and Computing, Congressus Numerantium, vol. 26, pp. 125\u2013157 (1979)"},{"issue":"2","key":"36_CR12","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1006\/jctb.1997.1812","volume":"72","author":"T Feder","year":"1998","unstructured":"Feder, T., Hell, P.: List homomorphisms to reflexive graphs. J. Comb. Theory Ser. B 72(2), 236\u2013250 (1998)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"4","key":"36_CR13","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1007\/s004939970003","volume":"19","author":"T Feder","year":"1999","unstructured":"Feder, T., Hell, P., Huang, J.: List homomorphisms and circular arc graphs. Combinatorica 19(4), 487\u2013505 (1999)","journal-title":"Combinatorica"},{"issue":"1","key":"36_CR14","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1002\/jgt.10073","volume":"42","author":"T Feder","year":"2003","unstructured":"Feder, T., Hell, P., Huang, J.: Bi-arc graphs and the complexity of list homomorphisms. J. Graph Theory 42(1), 61\u201380 (2003)","journal-title":"J. Graph Theory"},{"issue":"3","key":"36_CR15","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1137\/S0895480100384055","volume":"16","author":"T Feder","year":"2003","unstructured":"Feder, T., Hell, P., Klein, S., Motwani, R.: List partitions. SIAM J. Discret. Math. 16(3), 449\u2013478 (2003)","journal-title":"SIAM J. Discret. Math."},{"issue":"1","key":"36_CR16","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1016\/j.tcs.2005.09.030","volume":"349","author":"T Feder","year":"2005","unstructured":"Feder, T., Hell, P., Klein, S., Nogueira, L.T., Protti, F.: List matrix partitions of chordal graphs. Theor. Comput. Sci. 349(1), 52\u201366 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"36_CR17","doi-asserted-by":"crossref","unstructured":"Garey, M.R., Johnson, D.S., Stockmeyer, L.: Some simplified NP-complete problems. In: Proceedings of the Sixth Annual ACM Symposium on Theory of Computing, pp. 47\u201363 (1974)","DOI":"10.1145\/800119.803884"},{"key":"36_CR18","doi-asserted-by":"crossref","unstructured":"Garg, N., Papatriantafilou, M., Tsigas, P.: Distributed list coloring: how to dynamically allocate frequencies to mobile base stations. In: Proceedings of SPDP 1996: 8th IEEE Symposium on Parallel and Distributed Processing, pp. 18\u201325 (1996)","DOI":"10.1109\/SPDP.1996.570312"},{"issue":"1","key":"36_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., Kami\u0144ski, M., Lozin, V., Sawada, J., Shu, X.: Deciding $$k$$-colorability of $$P_5$$-free graphs in polynomial time. Algorithmica 57(1), 74\u201381 (2010)","journal-title":"Algorithmica"},{"issue":"2","key":"36_CR20","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)","journal-title":"Discret. Appl. Math."},{"key":"36_CR21","unstructured":"Kim, H., Siggers, M.: Towards a dichotomy for the switch list homomorphism problem for signed graphs. arXiv preprint arXiv:2104.07764 (2021)"},{"issue":"3","key":"36_CR22","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1016\/0166-218X(94)90150-3","volume":"50","author":"J Kratochvil","year":"1994","unstructured":"Kratochvil, J., Tuza, Z.: Algorithmic complexity of list colorings. Discret. Appl. Math. 50(3), 297\u2013302 (1994)","journal-title":"Discret. Appl. Math."},{"key":"36_CR23","unstructured":"Okrasa, K., Piecyk, M., Rzazewski, P.: Full complexity classification of the list homomorphism problem for bounded-treewidth graphs. In: 28th Annual European Symposium on Algorithms, ESA 2020, Pisa, Italy, 7\u20139 September 2020 (Virtual Conference), pp. 74:1\u201374:24 (2020)"},{"key":"36_CR24","unstructured":"Okrasa, K., Rzazewski, P.: Complexity of the list homomorphism problem in hereditary graph classes. In: Bl\u00e4ser, M., Monmege, B. (eds.) 38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021. LIPIcs, vol. 187, pp. 54:1\u201354:17 (2021)"},{"key":"36_CR25","unstructured":"Valadkhan, P.: List matrix partitions of special graphs. Ph.D. thesis, Applied Sciences: School of Computing Science (2013)"},{"key":"36_CR26","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/j.dam.2019.01.013","volume":"260","author":"P Valadkhan","year":"2019","unstructured":"Valadkhan, P.: List matrix partitions of graphs representing geometric configurations. Discret. Appl. Math. 260, 237\u2013243 (2019)","journal-title":"Discret. Appl. Math."},{"key":"36_CR27","first-page":"3","volume":"29","author":"VG Vizing","year":"1976","unstructured":"Vizing, V.G.: Vertex colorings with given colors. Diskret. Analiz 29, 3\u201310 (1976)","journal-title":"Diskret. Analiz"},{"key":"36_CR28","doi-asserted-by":"crossref","unstructured":"Wang, W., Liu, X.: List-coloring based channel allocation for open-spectrum wireless networks. In: VTC-2005-Fall. 2005 IEEE 62nd Vehicular Technology Conference, vol. 1, pp. 690\u2013694. Citeseer (2005)","DOI":"10.1109\/VETECF.2005.1558001"}],"container-title":["Lecture Notes in Computer Science","LATIN 2022: Theoretical Informatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-20624-5_36","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,6]],"date-time":"2024-10-06T19:56:19Z","timestamp":1728244579000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-20624-5_36"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783031206238","9783031206245"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-20624-5_36","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"29 October 2022","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"LATIN","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Latin American Symposium on Theoretical Informatics","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Guanajuato","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Mexico","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"7 November 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 November 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"latin2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/delta.cs.cinvestav.mx\/~francisco\/Latin22\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"114","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":"46","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":"40% - 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":"4","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":"8.7","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":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}