{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,7]],"date-time":"2026-06-07T08:49:29Z","timestamp":1780822169146,"version":"3.54.1"},"publisher-location":"Cham","reference-count":24,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031496134","type":"print"},{"value":"9783031496141","type":"electronic"}],"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-49614-1_29","type":"book-chapter","created":{"date-parts":[[2023,12,8]],"date-time":"2023-12-08T14:02:45Z","timestamp":1702044165000},"page":"390-402","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Critical $$(P_5,dart)$$-Free Graphs"],"prefix":"10.1007","author":[{"given":"Wen","family":"Xia","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jorik","family":"Jooken","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jan","family":"Goedgebeur","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shenwei","family":"Huang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2023,12,9]]},"reference":[{"key":"29_CR1","doi-asserted-by":"crossref","unstructured":"Bondy, J.A., Murty, U.S.R.: Graph Theory. Springer, Heidelberg (2008)","DOI":"10.1007\/978-1-84628-970-5"},{"key":"29_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"594","DOI":"10.1007\/978-3-642-10631-6_61","volume-title":"Algorithms and Computation","author":"D Bruce","year":"2009","unstructured":"Bruce, D., Ho\u00e0ng, C.T., Sawada, J.: A certifying algorithm for 3-colorability of $$P_5$$-free graphs. In: Dong, Y., Du, D.-Z., Ibarra, O. (eds.) ISAAC 2009. LNCS, vol. 5878, pp. 594\u2013604. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-10631-6_61"},{"key":"29_CR3","doi-asserted-by":"crossref","unstructured":"Coolsaet, K., D\u2019hondt, S., Goedgebeur, J.: House of graphs 2.0: a database of interesting graphs and more. Discrete Appl. Math. 325, 97\u2013107 (2023)","DOI":"10.1016\/j.dam.2022.10.013"},{"key":"29_CR4","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/j.dam.2023.03.008","volume":"334","author":"Q Cai","year":"2023","unstructured":"Cai, Q., Goedgebeur, J., Huang, S.: Some results on $$k$$-critical $$P_5$$-free graphs. Discrete Appl. Math. 334, 91\u2013100 (2023)","journal-title":"Discrete Appl. Math."},{"key":"29_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/978-3-030-18126-0_10","volume-title":"Frontiers in Algorithmics","author":"Q Cai","year":"2019","unstructured":"Cai, Q., Huang, S., Li, T., Shi, Y.: Vertex-critical ($$P_5$$, banner)-free graphs. In: Chen, Y., Deng, X., Lu, M. (eds.) FAW 2019. LNCS, vol. 11458, pp. 111\u2013120. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-18126-0_10"},{"key":"29_CR6","doi-asserted-by":"publisher","first-page":"113936","DOI":"10.1016\/j.tcs.2023.113936","volume":"961","author":"B Cameron","year":"2023","unstructured":"Cameron, B., Ho\u00e0ng, C.T.: A refinement on the structure of vertex-critical $$({P}_5, gem)$$-free graphs. Theoret. Comput. Sci. 961, 113936 (2023)","journal-title":"Theoret. Comput. Sci."},{"key":"29_CR7","doi-asserted-by":"crossref","unstructured":"Cameron, B. and Ho\u00e0ng, C. T.: Infinite families of $$k$$-vertex-critical ($$P_5, C_5$$)-free graphs. arXiv arXiv:2306.03376v1 [math.CO] (2023)","DOI":"10.1007\/s00373-024-02756-x"},{"key":"29_CR8","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1016\/j.tcs.2021.02.029","volume":"864","author":"K Cameron","year":"2021","unstructured":"Cameron, K., Goedgebeur, J., Huang, S., Shi, Y.: $$k$$-critical graphs in $$P_5$$-free graphs. Theoret. Comput. Sci. 864, 80\u201391 (2021)","journal-title":"Theoret. Comput. Sci."},{"key":"29_CR9","doi-asserted-by":"publisher","first-page":"51","DOI":"10.4007\/annals.2006.164.51","volume":"164","author":"M Chudnovsky","year":"2006","unstructured":"Chudnovsky, M., Robertson, N., Seymour, P., Thomas, R.: The strong perfect graph theorem. Ann. Math. 164, 51\u2013229 (2006)","journal-title":"Ann. Math."},{"key":"29_CR10","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1016\/j.dam.2016.05.018","volume":"216","author":"HS Dhaliwal","year":"2017","unstructured":"Dhaliwal, H.S., Hamel, A.M., Ho\u00e0ng, C.T., Maffray, F., McConnell, T.J.D., Panait, S.A.: On color-critical ($${P}_5$$, co-$${P_5}$$)-free graphs. Discrete Appl. Math. 216, 142\u2013148 (2017)","journal-title":"Discrete Appl. Math."},{"key":"29_CR11","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/0012-365X(93)90539-6","volume":"121","author":"JL Fouquet","year":"1993","unstructured":"Fouquet, J.L.: A decomposition for a class of $$(P_5,\\overline{P_5})$$-free graphs. Discrete Math. 121, 75\u201383 (1993)","journal-title":"Discrete Math."},{"key":"29_CR12","unstructured":"Goedgebeur, J.: Homepage of generator for $$k$$-critical $$\\cal{H} $$-free graphs. https:\/\/caagt.ugent.be\/criticalpfree\/"},{"key":"29_CR13","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1002\/jgt.22151","volume":"87","author":"J Goedgebeur","year":"2018","unstructured":"Goedgebeur, J., Schaudt, O.: Exhaustive generation of $$k$$-critical $$\\cal{H} $$-free graphs. J. Graph Theor. 87, 188\u2013207 (2018)","journal-title":"J. Graph Theor."},{"key":"29_CR14","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)","journal-title":"Discrete Appl. Math."},{"key":"29_CR15","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.V., Sawada, J., Shu, X.: Deciding $$k$$-colorability of $$P_5$$-free graphs in polynomial time. Algorithmica 57, 74\u201381 (2010)","journal-title":"Algorithmica"},{"key":"29_CR16","doi-asserted-by":"crossref","unstructured":"Ho\u00e0ng, C. T., Moore, B., Recoskiez, D., Sawada, J., Vatshelle. M.: Constructions of $$k$$-critical $${P_5}$$-free graphs. Discrete Appl. Math. 182, 91\u201398, (2015)","DOI":"10.1016\/j.dam.2014.06.007"},{"key":"29_CR17","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/j.dam.2023.02.019","volume":"334","author":"S Huang","year":"2023","unstructured":"Huang, S., Li, J., Xia, W.: Critical ($$P_5, bull$$)-free graphs. Discrete Appl. Math. 334, 15\u201325 (2023)","journal-title":"Discrete Appl. Math."},{"key":"29_CR18","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/j.dam.2018.11.010","volume":"258","author":"S Huang","year":"2019","unstructured":"Huang, S., Li, T., Shi, Y.: Critical ($$P_6$$, banner)-free graphs. Discrete Appl. Math. 258, 143\u2013151 (2019)","journal-title":"Discrete Appl. Math."},{"key":"29_CR19","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1016\/j.dam.2023.07.014","volume":"341","author":"S Huang","year":"2023","unstructured":"Huang, S., Li, Z.: Vertex-critical ($$P_5, chair$$)-free graphs. Discrete Appl. Math. 341, 9\u201315 (2023)","journal-title":"Discrete Appl. Math."},{"key":"29_CR20","unstructured":"Jooken, J.: GitHub page containing generator for $$k$$-vertex-critical $$\\cal{H} $$-free graphs. https:\/\/github.com\/JorikJooken\/kVertexCriticalGraphs"},{"key":"29_CR21","doi-asserted-by":"publisher","first-page":"258","DOI":"10.1016\/j.dam.2018.09.031","volume":"261","author":"M Kami\u0144ski","year":"2019","unstructured":"Kami\u0144ski, M., Pstrucha, A.: Certifying coloring algorithms for graphs without long induced paths. Discrete Appl. Math. 261, 258\u2013267 (2019)","journal-title":"Discrete Appl. Math."},{"key":"29_CR22","doi-asserted-by":"publisher","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W., Bohlinger, J.D. (eds.) Complexity of Computer Computations. The IBM Research Symposia Series. Springer, Boston (1972). https:\/\/doi.org\/10.1007\/978-1-4684-2001-2_9","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"29_CR23","doi-asserted-by":"publisher","first-page":"1682","DOI":"10.1137\/110829222","volume":"26","author":"F Maffray","year":"2012","unstructured":"Maffray, F., Morel, G.: On 3-colorable $$P_5$$-free graphs. SIAM J. Discrete Math. 26, 1682\u20131708 (2012)","journal-title":"SIAM J. Discrete Math."},{"key":"29_CR24","doi-asserted-by":"crossref","unstructured":"Xia, W., Jooken, J., Goedgebeur, J., Huang, S.: Critical $$(P_5, dart)$$-Free Graphs. arXiv arXiv:2308.03414v2 [math.CO] (2023)","DOI":"10.1007\/978-3-031-49614-1_29"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-49614-1_29","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,5]],"date-time":"2024-11-05T16:50:50Z","timestamp":1730825450000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-49614-1_29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,9]]},"ISBN":["9783031496134","9783031496141"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-49614-1_29","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"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":"COCOA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Combinatorial Optimization and Applications","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Hawai, 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":"16","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cocoa2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/theory.utdallas.edu\/COCOA2023\/","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":"EquinOCS","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"117","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":"73","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":"62% - 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":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}