{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,26]],"date-time":"2026-06-26T12:15:46Z","timestamp":1782476146393,"version":"3.54.5"},"reference-count":17,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,4,16]],"date-time":"2021-04-16T00:00:00Z","timestamp":1618531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,4,16]],"date-time":"2021-04-16T00:00:00Z","timestamp":1618531200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11871034"],"award-info":[{"award-number":["11871034"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2021,7]]},"DOI":"10.1007\/s10878-021-00742-0","type":"journal-article","created":{"date-parts":[[2021,4,16]],"date-time":"2021-04-16T07:07:13Z","timestamp":1618556833000},"page":"40-55","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Complexity results for two kinds of colored disconnections of graphs"],"prefix":"10.1007","volume":"42","author":[{"given":"You","family":"Chen","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ping","family":"Li","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8335-9873","authenticated-orcid":false,"given":"Xueliang","family":"Li","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yindi","family":"Weng","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2021,4,16]]},"reference":[{"key":"742_CR1","first-page":"189","volume":"97","author":"E Andrews","year":"2016","unstructured":"Andrews E, Laforge E, Lumduanhom C, Zhang P (2016) On proper-path colorings in graphs. J Comb Math Comb Comput 97:189\u2013207","journal-title":"J Comb Math Comb Comput"},{"key":"742_CR2","unstructured":"Bai X, Li X (2020) Graph colorings under global structural conditions. arXiv:2008.07163 [math.CO]"},{"key":"742_CR3","doi-asserted-by":"publisher","DOI":"10.7151\/dmgt.2333","author":"X Bai","year":"2018","unstructured":"Bai X, Chang R, Huang Z, Li X (2018) More on rainbow disconnection in graphs. Discuss Math Graph Theory. https:\/\/doi.org\/10.7151\/dmgt.2333","journal-title":"Discuss Math Graph Theory"},{"key":"742_CR4","doi-asserted-by":"crossref","unstructured":"Bai X, Huang Z, Li X (2020) Bounds for the rainbow disconnection number of graphs. arXiv:2003.13237 [math.CO]","DOI":"10.7151\/dmgt.2333"},{"key":"742_CR5","doi-asserted-by":"publisher","DOI":"10.1007\/s40840-020-01069-5","author":"X Bai","year":"2021","unstructured":"Bai X, Chen Y, Ji M, Li X, Weng Y, Wu W (2021a) Proper disconnection in graphs. Bull Malays Math Sci Soc. https:\/\/doi.org\/10.1007\/s40840-020-01069-5","journal-title":"Bull Malays Math Sci Soc"},{"key":"742_CR6","doi-asserted-by":"publisher","DOI":"10.1007\/s10114-020-0083-x","author":"X Bai","year":"2021","unstructured":"Bai X, Chen Y, Li P, Li X, Weng Y (2021b) The rainbow vertex-disconnection in graphs. Acta Math Sin (Engl Ser). https:\/\/doi.org\/10.1007\/s10114-020-0083-x","journal-title":"Acta Math Sin (Engl Ser)"},{"key":"742_CR7","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-84628-970-5","volume-title":"Graph theory","author":"JA Bondy","year":"2008","unstructured":"Bondy JA, Murty USR (2008) Graph theory. Springer, Berlin"},{"key":"742_CR8","doi-asserted-by":"publisher","first-page":"2550","DOI":"10.1016\/j.disc.2011.09.003","volume":"312","author":"V Borozan","year":"2012","unstructured":"Borozan V, Fujita S, Gerek A, Magnant C, Manoussakis Y, Montero L, Zs T (2012) Proper connection of graphs. Discrete Math 312:2550\u20132560","journal-title":"Discrete Math"},{"key":"742_CR9","volume-title":"Restricted colorings of graphs","author":"J Cai","year":"2019","unstructured":"Cai J, Wang J, Zhang X (2019) Restricted colorings of graphs. Science Press, Beijing"},{"key":"742_CR10","doi-asserted-by":"publisher","first-page":"85","DOI":"10.21136\/MB.2008.133947","volume":"133","author":"G Chartrand","year":"2008","unstructured":"Chartrand G, Johns GL, McKeon KA, Zhang P (2008) Rainbow connection in graphs. Math Bohem 133:85\u201398","journal-title":"Math Bohem"},{"key":"742_CR11","doi-asserted-by":"publisher","first-page":"1007","DOI":"10.7151\/dmgt.2061","volume":"38","author":"G Chartrand","year":"2018","unstructured":"Chartrand G, Devereaux S, Haynes TW, Hedetniemi ST, Zhang P (2018) Rainbow disconnection in graphs. Discuss Math Graph Theory 38:1007\u20131021","journal-title":"Discuss Math Graph Theory"},{"key":"742_CR12","doi-asserted-by":"crossref","unstructured":"Chen Y, Li P, Li X, Weng Y (2020) Complexity results for the proper disconnection of graphs. In: Proceedings of 14th international frontiers of algorithmics workshop (FAW 2020), LNCS No.12340, pp 1\u201312","DOI":"10.1007\/978-3-030-59901-0_1"},{"key":"742_CR13","doi-asserted-by":"crossref","unstructured":"Darmann A, D\u00f6cker J (2019) On simplified NP-complete variants of Not-All-Equal 3-SAT and 3-SAT. arXiv:1908.04198 [cs.CC]","DOI":"10.1016\/j.tcs.2020.02.010"},{"key":"742_CR14","doi-asserted-by":"crossref","unstructured":"Li X, Weng Y (2020) Further results on the rainbow vertex-disconnection of graphs. arXiv:2004.06285 [math.CO]","DOI":"10.1007\/s40840-021-01125-8"},{"key":"742_CR15","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1002\/jgt.3190130502","volume":"13","author":"AM Moshi","year":"1989","unstructured":"Moshi AM (1989) Matching cutsets in graphs. J Graph Theory 13:527\u2013536","journal-title":"J Graph Theory"},{"key":"742_CR16","doi-asserted-by":"crossref","unstructured":"Patrignani M, Pizzonia M (2001) The complexity of the matching-cut problem. In: Brandst\u00e4dt A, Le VB (eds) Graph-theoretic concepts in computer science. WG 2001. LNCS No. 2204, pp 284\u2013295","DOI":"10.1007\/3-540-45477-2_26"},{"key":"742_CR17","doi-asserted-by":"crossref","unstructured":"Schaefer TJ (1978) The complexity of satisfiability problems. In: Proceedings of the 10th annual ACM symposium on theory of computing. ACM, New York, pp 216\u2013226","DOI":"10.1145\/800133.804350"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-021-00742-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-021-00742-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-021-00742-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,12]],"date-time":"2021-07-12T05:10:46Z","timestamp":1626066646000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-021-00742-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,4,16]]},"references-count":17,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,7]]}},"alternative-id":["742"],"URL":"https:\/\/doi.org\/10.1007\/s10878-021-00742-0","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,4,16]]},"assertion":[{"value":"8 April 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 April 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}