{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T14:06:38Z","timestamp":1742911598585,"version":"3.40.3"},"publisher-location":"Cham","reference-count":33,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030868376"},{"type":"electronic","value":"9783030868383"}],"license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"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":[[2021]]},"DOI":"10.1007\/978-3-030-86838-3_30","type":"book-chapter","created":{"date-parts":[[2021,9,19]],"date-time":"2021-09-19T22:05:30Z","timestamp":1632089130000},"page":"388-401","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["On 3-Coloring of $$(2P_4,C_5)$$-Free Graphs"],"prefix":"10.1007","author":[{"given":"V\u00edt","family":"Jel\u00ednek","sequence":"first","affiliation":[]},{"given":"Tereza","family":"Klimo\u0161ov\u00e1","sequence":"additional","affiliation":[]},{"given":"Tom\u00e1\u0161","family":"Masa\u0159\u00edk","sequence":"additional","affiliation":[]},{"given":"Jana","family":"Novotn\u00e1","sequence":"additional","affiliation":[]},{"given":"Aneta","family":"Pokorn\u00e1","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,9,20]]},"reference":[{"issue":"4","key":"30_CR1","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., Steinz, M., Zhong, M.: Three-coloring and list three-coloring of graphs without induced paths on seven vertices. Combinatorica 38(4), 779\u2013801 (2018). https:\/\/doi.org\/10.1007\/s00493-017-3553-8","journal-title":"Combinatorica"},{"key":"30_CR2","unstructured":"Bonomo, F., Schaudt, O., Stein, M.: 3-colouring graphs without triangles or induced paths on seven vertices. CoRR (2014). https:\/\/arxiv.org\/abs\/1410.0040v1"},{"key":"30_CR3","doi-asserted-by":"publisher","unstructured":"Bonomo-Braberman, F., et al.: Better 3-coloring algorithms: excluding a triangle and a seven vertex path. Theoret. Comput. Sci. 850, 98\u2013115 (2020). https:\/\/doi.org\/10.1016\/j.tcs.2020.10.032","DOI":"10.1016\/j.tcs.2020.10.032"},{"issue":"1","key":"30_CR4","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/0095-8956(79)90067-4","volume":"27","author":"CA Christen","year":"1979","unstructured":"Christen, C.A., Selkow, S.M.: Some perfect coloring properties of graphs. J. Comb. Theory Ser. B 27(1), 49\u201359 (1979). https:\/\/doi.org\/10.1016\/0095-8956(79)90067-4","journal-title":"J. Comb. Theory Ser. B"},{"issue":"1","key":"30_CR5","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1007\/s00453-020-00754-y","volume":"83","author":"M Chudnovsky","year":"2020","unstructured":"Chudnovsky, M., Huang, S., Spirkl, S., Zhong, M.: List 3-coloring graphs with no induced $$P_6+rP_3$$. Algorithmica 83(1), 216\u2013251 (2020). https:\/\/doi.org\/10.1007\/s00453-020-00754-y","journal-title":"Algorithmica"},{"issue":"3","key":"30_CR6","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1002\/jgt.22025","volume":"84","author":"M Chudnovsky","year":"2017","unstructured":"Chudnovsky, M., Maceli, P., Stacho, J., Zhong, M.: 4-coloring $$P_6$$-free graphs with no induced 5-cycles. J. Graph Theory 84(3), 262\u2013285 (2017). https:\/\/doi.org\/10.1002\/jgt.22025","journal-title":"J. Graph Theory"},{"key":"30_CR7","unstructured":"Chudnovsky, M., Maceli, P., Zhong, M.: Three-coloring graphs with no induced seven-vertex path I: the triangle-free case. CoRR (2014). https:\/\/arxiv.org\/abs\/1409.5164"},{"key":"30_CR8","unstructured":"Chudnovsky, M., Maceli, P., Zhong, M.: Three-coloring graphs with no induced seven-vertex path II: using a triangle. CoRR (2015). https:\/\/arxiv.org\/abs\/1503.03573"},{"key":"30_CR9","doi-asserted-by":"crossref","unstructured":"Chudnovsky, M., Robertson, N., Seymour, P., Thomas, R.: The strong perfect graph theorem. Ann. Math. 164(1), 51\u2013229 (2006). http:\/\/www.jstor.org\/stable\/20159988","DOI":"10.4007\/annals.2006.164.51"},{"key":"30_CR10","doi-asserted-by":"publisher","unstructured":"Chudnovsky, M., Spirkl, S., Zhong, M.: List-three-coloring $${P}_t$$-free graphs with no induced 1-subdivision of $${K}_{1,s}$$. Discrete Math. 343(11), 112086 (2020). https:\/\/doi.org\/10.1016\/j.disc.2020.112086","DOI":"10.1016\/j.disc.2020.112086"},{"issue":"2","key":"30_CR11","doi-asserted-by":"publisher","first-page":"1111","DOI":"10.1137\/16m1104858","volume":"32","author":"M Chudnovsky","year":"2018","unstructured":"Chudnovsky, M., Stacho, J.: 3-colorable subclasses of $${P}_8$$-free graphs. SIAM J. Discrete Math. 32(2), 1111\u20131138 (2018). https:\/\/doi.org\/10.1137\/16m1104858","journal-title":"SIAM J. Discrete Math."},{"issue":"1","key":"30_CR12","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/0166-218x(84)90088-x","volume":"9","author":"DG Corneil","year":"1984","unstructured":"Corneil, D.G., Perl, Y.: Clustering and domination in perfect graphs. Discrete Appl. Math. 9(1), 27\u201339 (1984). https:\/\/doi.org\/10.1016\/0166-218x(84)90088-x","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"30_CR13","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1007\/s00453-013-9777-0","volume":"71","author":"JF Couturier","year":"2013","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 (2013). https:\/\/doi.org\/10.1007\/s00453-013-9777-0","journal-title":"Algorithmica"},{"issue":"4","key":"30_CR14","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1017\/S0963548398003678","volume":"7","author":"T Emden-Weinert","year":"1998","unstructured":"Emden-Weinert, T., Hougardy, S., Kreuter, B.: Uniquely colourable graphs and the hardness of colouring graphs of large girth. Comb. Probab. Comput. 7(4), 375\u2013386 (1998). https:\/\/doi.org\/10.1017\/S0963548398003678","journal-title":"Comb. Probab. Comput."},{"key":"30_CR15","doi-asserted-by":"publisher","unstructured":"Gartland, P., Lokshtanov, D.: Independent set on $${P}_{k}$$-free graphs in quasi-polynomial time. In: 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, 16\u201319 November 2020, pp. 613\u2013624. IEEE (2020). https:\/\/doi.org\/10.1109\/FOCS46700.2020.00063","DOI":"10.1109\/FOCS46700.2020.00063"},{"issue":"2","key":"30_CR16","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1002\/jgt.22151","volume":"87","author":"J Goedgebeur","year":"2017","unstructured":"Goedgebeur, J., Schaudt, O.: Exhaustive generation of k-critical H-free graphs. J. Graph Theory 87(2), 188\u2013207 (2017). https:\/\/doi.org\/10.1002\/jgt.22151","journal-title":"J. Graph Theory"},{"issue":"4","key":"30_CR17","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1002\/jgt.22028","volume":"84","author":"PA Golovach","year":"2016","unstructured":"Golovach, P.A., Johnson, M., Paulusma, D., Song, J.: A survey on the computational complexity of coloring graphs with forbidden subgraphs. J. Graph Theory 84(4), 331\u2013363 (2016). https:\/\/doi.org\/10.1002\/jgt.22028","journal-title":"J. Graph Theory"},{"key":"30_CR18","doi-asserted-by":"publisher","first-page":"204","DOI":"10.1016\/j.ic.2014.02.004","volume":"237","author":"PA Golovach","year":"2014","unstructured":"Golovach, P.A., Paulusma, D., Song, J.: Closing complexity gaps for coloring problems on H-free graphs. Inf. Comput. 237, 204\u2013214 (2014). https:\/\/doi.org\/10.1016\/j.ic.2014.02.004","journal-title":"Inf. Comput."},{"key":"30_CR19","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/j.dam.2013.12.008","volume":"167","author":"PA Golovach","year":"2014","unstructured":"Golovach, P.A., Paulusma, D., Song, J.: Coloring graphs without short cycles and long induced paths. Discrete Appl. Math. 167, 107\u2013120 (2014). https:\/\/doi.org\/10.1016\/j.dam.2013.12.008","journal-title":"Discrete Appl. Math."},{"key":"30_CR20","doi-asserted-by":"publisher","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Polynomial algorithms for perfect graphs. In: Topics on Perfect Graphs, pp. 325\u2013356. Elsevier (1984). https:\/\/doi.org\/10.1016\/s0304-0208(08)72943-8","DOI":"10.1016\/s0304-0208(08)72943-8"},{"key":"30_CR21","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1016\/j.dam.2015.10.024","volume":"216","author":"P Hell","year":"2017","unstructured":"Hell, P., Huang, S.: Complexity of coloring graphs without paths and cycles. Discrete Appl. Math. 216, 211\u2013232 (2017). https:\/\/doi.org\/10.1016\/j.dam.2015.10.024","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"30_CR22","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1007\/s00453-008-9197-8","volume":"57","author":"CT Ho\u00e0ng","year":"2008","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 (2008). https:\/\/doi.org\/10.1007\/s00453-008-9197-8","journal-title":"Algorithmica"},{"issue":"4","key":"30_CR23","doi-asserted-by":"publisher","first-page":"718","DOI":"10.1137\/0210055","volume":"10","author":"I Holyer","year":"1981","unstructured":"Holyer, I.: The NP-completeness of edge-coloring. SIAM J. Comput. 10(4), 718\u2013720 (1981). https:\/\/doi.org\/10.1137\/0210055","journal-title":"SIAM J. Comput."},{"key":"30_CR24","doi-asserted-by":"publisher","first-page":"336","DOI":"10.1016\/j.ejc.2015.06.005","volume":"51","author":"S Huang","year":"2016","unstructured":"Huang, S.: Improved complexity results on k-coloring $${P}_t$$-free graphs. Eur. J. Comb. 51, 336\u2013346 (2016). https:\/\/doi.org\/10.1016\/j.ejc.2015.06.005","journal-title":"Eur. J. Comb."},{"issue":"11","key":"30_CR25","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 colouring $$({C}_s, {P}_t)$$-free graphs. Comput. J. 58(11), 3074\u20133088 (2015). https:\/\/doi.org\/10.1093\/comjnl\/bxv039","journal-title":"Comput. J."},{"key":"30_CR26","doi-asserted-by":"crossref","unstructured":"Jel\u00ednek, V., Klimo\u0161ov\u00e1, T., Masa\u0159\u00edk, T., Novotn\u00e1, J., Pokorn\u00e1, A.: Note on 3-coloring of $$(2{P}_4,{C}_5)$$-free graphs. CoRR (2020). https:\/\/arxiv.org\/abs\/2011.06173","DOI":"10.1007\/978-3-030-86838-3_30"},{"key":"30_CR27","doi-asserted-by":"publisher","unstructured":"Karp, R.M.: Reducibility among Combinatorial Problems, pp. 85\u2013103. Springer, Boston (1972). https:\/\/doi.org\/10.1007\/978-1-4684-2001-2_9","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"30_CR28","doi-asserted-by":"publisher","unstructured":"Klimo\u0161ov\u00e1, T., Mal\u00edk, J., Masa\u0159\u00edk, T., Novotn\u00e1, J., Paulusma, D., Sl\u00edvov\u00e1, V.: Colouring ($${P}_r+{P}_s$$)-free graphs. Algorithmica 82(7), 1833\u20131858 (2020). https:\/\/doi.org\/10.1007\/s00453-020-00675-w","DOI":"10.1007\/s00453-020-00675-w"},{"issue":"1\u20132","key":"30_CR29","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1002\/malq.19670130104","volume":"13","author":"MR Krom","year":"1967","unstructured":"Krom, M.R.: The decision problem for a class of first-order formulas in which all disjunctions are binary. Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik 13(1\u20132), 15\u201320 (1967). https:\/\/doi.org\/10.1002\/malq.19670130104","journal-title":"Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik"},{"issue":"1","key":"30_CR30","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/0196-6774(83)90032-9","volume":"4","author":"D Leven","year":"1983","unstructured":"Leven, D., Galil, Z.: NP completeness of finding the chromatic index of regular graphs. J. Algorithms 4(1), 35\u201344 (1983). https:\/\/doi.org\/10.1016\/0196-6774(83)90032-9","journal-title":"J. Algorithms"},{"key":"30_CR31","doi-asserted-by":"publisher","unstructured":"Pilipczuk, M., Pilipczuk, M., Rz\u0105\u017cewski, P.: Quasi-polynomial-time algorithm for independent set in $${P}_t$$-free graphs via shrinking the space of induced paths. In: Symposium on Simplicity in Algorithms (SOSA), pp. 204\u2013209. Society for Industrial and Applied Mathematics, January 2021. https:\/\/doi.org\/10.1137\/1.9781611976496.23","DOI":"10.1137\/1.9781611976496.23"},{"key":"30_CR32","unstructured":"Rojas, A., Stein, M.: $$3$$-colouring $$P_t$$-free graphs without short odd cycles. CoRR (2020). https:\/\/arxiv.org\/abs\/2008.04845"},{"key":"30_CR33","doi-asserted-by":"publisher","unstructured":"Spirkl, S., Chudnovsky, M., Zhong, M.: Four-coloring $${P}_6$$-free graphs. In: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1239\u20131256. Society for Industrial and Applied Mathematics, January 2019. https:\/\/doi.org\/10.1137\/1.9781611975482.76","DOI":"10.1137\/1.9781611975482.76"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-86838-3_30","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,12,8]],"date-time":"2023-12-08T20:04:16Z","timestamp":1702065856000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-86838-3_30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030868376","9783030868383"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-86838-3_30","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"20 September 2021","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WG","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Graph-Theoretic Concepts in Computer Science","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Warsaw","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Poland","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2021","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23 June 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"25 June 2021","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"47","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wg2021","order":10,"name":"conference_id","label":"Conference ID","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 and OCS","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"73","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":"30","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":"11","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)"}},{"value":"The conference was held online due to the COVID-19 pandemic.","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}