{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,15]],"date-time":"2026-07-15T10:12:21Z","timestamp":1784110341404,"version":"3.55.0"},"publisher-location":"Singapore","reference-count":24,"publisher":"Springer Nature Singapore","isbn-type":[{"value":"9789819610891","type":"print"},{"value":"9789819610907","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"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":[[2025]]},"DOI":"10.1007\/978-981-96-1090-7_24","type":"book-chapter","created":{"date-parts":[[2025,3,4]],"date-time":"2025-03-04T16:32:41Z","timestamp":1741105961000},"page":"289-300","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["The Complexity of\u00a0Strong Conflict-Free Vertex-Connection k-colorability"],"prefix":"10.1007","author":[{"given":"Sun-Yuan","family":"Hsieh","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hoang-Oanh","family":"Le","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Van Bang","family":"Le","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sheng-Lung","family":"Peng","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2025,3,5]]},"reference":[{"issue":"12","key":"24_CR1","doi-asserted-by":"publisher","first-page":"3500","DOI":"10.1016\/J.DISC.2018.09.002","volume":"341","author":"C Brause","year":"2018","unstructured":"Brause, C., Jendrol\u2019, S., Schiermeyer, I.: Odd connection and odd vertex-connection of graphs. Discret. Math. 341(12), 3500\u20133512 (2018). https:\/\/doi.org\/10.1016\/J.DISC.2018.09.002","journal-title":"Discret. Math."},{"issue":"3","key":"24_CR2","doi-asserted-by":"publisher","first-page":"340","DOI":"10.1007\/S10878-018-0363-X","volume":"42","author":"H Chang","year":"2021","unstructured":"Chang, H., Ji, M., Li, X., Zhang, J.: Conflict-free connection of trees. J. Comb. Optim. 42(3), 340\u2013353 (2021). https:\/\/doi.org\/10.1007\/S10878-018-0363-X","journal-title":"J. Comb. Optim."},{"key":"24_CR3","doi-asserted-by":"publisher","unstructured":"Chartrand, G., Johns, G.L., McKeon, K.A., Zhang, P.: Rainbow connection in graphs. Mathematica Bohemica 133(1), 85\u201398 (2008). https:\/\/doi.org\/10.21136\/MB.2008.133947","DOI":"10.21136\/MB.2008.133947"},{"issue":"4","key":"24_CR4","doi-asserted-by":"publisher","first-page":"911","DOI":"10.7151\/DMGT.2036","volume":"38","author":"J Czap","year":"2018","unstructured":"Czap, J., Jendrol\u2019, S., Valiska, J.: Conflict-free connections of graphs. Discuss. Math. Graph Theory 38(4), 911\u2013920 (2018). https:\/\/doi.org\/10.7151\/DMGT.2036","journal-title":"Discuss. Math. Graph Theory"},{"issue":"3","key":"24_CR5","doi-asserted-by":"publisher","first-page":"2205","DOI":"10.1137\/21M1447714","volume":"36","author":"M Debski","year":"2022","unstructured":"Debski, M., Piecyk, M., Rzazewski, P.: Faster 3-coloring of small-diameter graphs. SIAM J. Discret. Math. 36(3), 2205\u20132224 (2022). https:\/\/doi.org\/10.1137\/21M1447714","journal-title":"SIAM J. Discret. Math."},{"key":"24_CR6","doi-asserted-by":"publisher","unstructured":"Doan, T.D., Ha, P.H., Schiermeyer, I.: The conflict-free vertex-connection number and degree conditions of graphs. Graphs Comb. 38(5), 157 (2022). https:\/\/doi.org\/10.1007\/S00373-022-02567-Y","DOI":"10.1007\/S00373-022-02567-Y"},{"issue":"2","key":"24_CR7","doi-asserted-by":"publisher","first-page":"617","DOI":"10.7151\/DMGT.2211","volume":"41","author":"TD Doan","year":"2021","unstructured":"Doan, T.D., Schiermeyer, I.: Conflict-free vertex connection number at most 3 and size of graphs. Discuss. Math. Graph Theory 41(2), 617\u2013632 (2021). https:\/\/doi.org\/10.7151\/DMGT.2211","journal-title":"Discuss. Math. Graph Theory"},{"issue":"1","key":"24_CR8","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1137\/S0097539702431840","volume":"33","author":"G Even","year":"2003","unstructured":"Even, G., Lotker, Z., Ron, D., Smorodinsky, S.: Conflict-free colorings of simple geometric regions with applications to frequency assignment in cellular networks. SIAM J. Comput. 33(1), 94\u2013136 (2003). https:\/\/doi.org\/10.1137\/S0097539702431840","journal-title":"SIAM J. Comput."},{"issue":"2","key":"24_CR9","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1006\/jcss.2000.1727","volume":"62","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R.: On the complexity of $$k$$-SAT. J. Comput. Syst. Sci. 62(2), 367\u2013375 (2001). https:\/\/doi.org\/10.1006\/jcss.2000.1727","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"24_CR10","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63(4), 512\u2013530 (2001). https:\/\/doi.org\/10.1006\/jcss.2001.1774","journal-title":"J. Comput. Syst. Sci."},{"key":"24_CR11","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1016\/j.ic.2013.08.005","volume":"231","author":"BMP Jansen","year":"2013","unstructured":"Jansen, B.M.P., Kratsch, S.: Data reduction for graph coloring problems. Inf. Comput. 231, 70\u201388 (2013). https:\/\/doi.org\/10.1016\/j.ic.2013.08.005","journal-title":"Inf. Comput."},{"key":"24_CR12","doi-asserted-by":"publisher","first-page":"124639","DOI":"10.1016\/J.AMC.2019.124639","volume":"364","author":"M Ji","year":"2020","unstructured":"Ji, M., Li, X.: Strong conflict-free connection of graphs. Appl. Math. Comput. 364, 124639 (2020). https:\/\/doi.org\/10.1016\/J.AMC.2019.124639","journal-title":"Appl. Math. Comput."},{"key":"24_CR13","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1016\/J.TCS.2019.10.043","volume":"804","author":"M Ji","year":"2020","unstructured":"Ji, M., Li, X., Zhu, X.: (Strong) conflict-free connectivity: algorithm and complexity. Theor. Comput. Sci. 804, 72\u201380 (2020). https:\/\/doi.org\/10.1016\/J.TCS.2019.10.043","journal-title":"Theor. Comput. Sci."},{"key":"24_CR14","doi-asserted-by":"publisher","unstructured":"Li, X., Magnant, C.: Properly colored notions of connectivity \u2013 a dynamic survey. Theory Appl. Graphs 0(1), Art. 2 (2015). https:\/\/doi.org\/10.20429\/tag.2015.000102","DOI":"10.20429\/tag.2015.000102"},{"issue":"1","key":"24_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/S00373-012-1243-2","volume":"29","author":"X Li","year":"2013","unstructured":"Li, X., Shi, Y., Sun, Y.: Rainbow connections of graphs: a survey. Graphs Comb. 29(1), 1\u201338 (2013). https:\/\/doi.org\/10.1007\/S00373-012-1243-2","journal-title":"Graphs Comb."},{"key":"24_CR16","doi-asserted-by":"publisher","unstructured":"Li, X., Sun, Y.: An updated survey on rainbow connections of graphs \u2013 a dynamic survey. Theory Appl. Graphs 0(1), Art. 2 (2017). https:\/\/doi.org\/10.20429\/tag.2017.000103","DOI":"10.20429\/tag.2017.000103"},{"key":"24_CR17","doi-asserted-by":"publisher","unstructured":"Li, X., Wu, D.: A survey on monochromatic connections of graphs. Theory Appl. Graphs 0(1), Art. 4 (2018). https:\/\/doi.org\/10.20429\/tag.2017.000104","DOI":"10.20429\/tag.2017.000104"},{"issue":"1","key":"24_CR18","doi-asserted-by":"publisher","first-page":"51","DOI":"10.7151\/DMGT.2116","volume":"40","author":"X Li","year":"2020","unstructured":"Li, X., Zhang, Y., Zhu, X., Mao, Y., Zhao, H., Jendrol\u2019, S.: Conflict-free vertex-connections of graphs. Discuss. Math. Graph Theory 40(1), 51\u201365 (2020). https:\/\/doi.org\/10.7151\/DMGT.2116","journal-title":"Discuss. Math. Graph Theory"},{"key":"24_CR19","unstructured":"Li, X., Zhu, X.: Conflict-free (vertex-)connection numbers of graphs with small diameters. Australas. J. Comb. 76, 288\u2013298 (2020). http:\/\/ajc.maths.uq.edu.au\/pdf\/76\/ajc_v76_p288.pdf"},{"key":"24_CR20","doi-asserted-by":"publisher","unstructured":"Li, Z., Wu, B.: Maximum value of conflict-free vertex-connection number of graphs. Discret. Math. Algorithms Appl. 10(5), 1850059:1\u20131850059:6 (2018). https:\/\/doi.org\/10.1142\/S1793830918500593","DOI":"10.1142\/S1793830918500593"},{"issue":"3","key":"24_CR21","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1007\/S00373-023-02649-5","volume":"39","author":"Z Li","year":"2023","unstructured":"Li, Z., Baoyindureng, W.: Conflict-free connection number of graphs with four bridges. Graphs Comb. 39(3), 50 (2023). https:\/\/doi.org\/10.1007\/S00373-023-02649-5","journal-title":"Graphs Comb."},{"key":"24_CR22","unstructured":"Lokshtanov, D., Marx, D., Saurabh, S.: Lower bounds based on the exponential time hypothesis. Bull. EATCS 105, 41\u201372 (2011). http:\/\/eatcs.org\/beatcs\/index.php\/beatcs\/article\/view\/92"},{"issue":"1","key":"24_CR23","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1007\/S00453-014-9949-6","volume":"74","author":"GB Mertzios","year":"2016","unstructured":"Mertzios, G.B., Spirakis, P.G.: Algorithms and almost tight results for 3-colorability of small diameter graphs. Algorithmica 74(1), 385\u2013414 (2016). https:\/\/doi.org\/10.1007\/S00453-014-9949-6","journal-title":"Algorithmica"},{"key":"24_CR24","doi-asserted-by":"publisher","unstructured":"Smorodinsky, S.: Conflict-free coloring and its applications. In: B\u00e1r\u00e1ny, I., B\u00f6r\u00f6czky, K.J., T\u00f3th, G.F., Pach, J. (eds.) Geometry\u2014Intuitive, Discrete, and Convex. BSMS, vol. 24, pp. 331\u2013389. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-41498-5_12","DOI":"10.1007\/978-3-642-41498-5_12"}],"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-981-96-1090-7_24","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,7]],"date-time":"2025-08-07T11:50:39Z","timestamp":1754567439000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-981-96-1090-7_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9789819610891","9789819610907"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-981-96-1090-7_24","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"5 March 2025","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":"Shanghai","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23 August 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"25 August 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"30","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cocoon2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/anl.sjtu.edu.cn\/cocoon2024\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}