{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,13]],"date-time":"2025-03-13T17:40:12Z","timestamp":1741887612569,"version":"3.38.0"},"reference-count":29,"publisher":"Wiley","issue":"1","license":[{"start":{"date-parts":[[2025,1,8]],"date-time":"2025-01-08T00:00:00Z","timestamp":1736294400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["Journal of Graph Theory"],"published-print":{"date-parts":[[2025,5]]},"abstract":"<jats:title>ABSTRACT<\/jats:title><jats:p>Deciding whether a graph can be edge\u2010decomposed into a matching and a \u2010bounded linear forest was recently shown by Campbell, H\u00f6rsch, and Moore to be nonedeterministic Polynomial time (NP)\u2010complete for every , and solvable in polynomial time for . In the first part of this paper, we close this gap by showing that this problem is NP\u2010complete for every . In the second part of the paper, we show that deciding whether a graph can be edge\u2010decomposed into a matching and a \u2010bounded star forest is polynomially solvable for any , answering another question by Campbell, H\u00f6rsch, and Moore from the same paper.<\/jats:p>","DOI":"10.1002\/jgt.23208","type":"journal-article","created":{"date-parts":[[2025,1,9]],"date-time":"2025-01-09T05:22:31Z","timestamp":1736400151000},"page":"76-87","update-policy":"https:\/\/doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["The Complexity of Decomposing a Graph into a Matching and a Bounded Linear Forest"],"prefix":"10.1002","volume":"109","author":[{"given":"Agnijo","family":"Banerjee","sequence":"first","affiliation":[{"name":"Department of Pure Mathematics and Mathematical Statistics (DPMMS) University of Cambridge Cambridge UK"}],"role":[{"role":"author","vocab":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-5539-9061","authenticated-orcid":false,"given":"Jo\u00e3o Pedro","family":"Marciano","sequence":"additional","affiliation":[{"name":"Instituto Nacional de Matem\u00e1tica Pura e Aplicada (IMPA) Jardim Bot\u00e2nico Rio de Janeiro RJ Brazil"}],"role":[{"role":"author","vocab":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4805-7503","authenticated-orcid":false,"given":"Adva","family":"Mond","sequence":"additional","affiliation":[{"name":"Department of Pure Mathematics and Mathematical Statistics (DPMMS) University of Cambridge Cambridge UK"}],"role":[{"role":"author","vocab":"crossref"}]},{"given":"Jan","family":"Petr","sequence":"additional","affiliation":[{"name":"Department of Pure Mathematics and Mathematical Statistics (DPMMS) University of Cambridge Cambridge UK"}],"role":[{"role":"author","vocab":"crossref"}]},{"given":"Julien","family":"Portier","sequence":"additional","affiliation":[{"name":"Department of Pure Mathematics and Mathematical Statistics (DPMMS) University of Cambridge Cambridge UK"}],"role":[{"role":"author","vocab":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2025,1,8]]},"reference":[{"key":"e_1_2_7_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/129712.129737"},{"key":"e_1_2_7_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01956769"},{"key":"e_1_2_7_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01903577"},{"volume-title":"The Decomposition of Graphs Into Ladder Graphs","year":"1980","author":"Brouwer A. E.","key":"e_1_2_7_5_1"},{"key":"e_1_2_7_6_1","first-page":"125","article-title":"Decomposition of Graphs Into Graphs With Three Edges","volume":"20","author":"Favaron O.","year":"1985","journal-title":"Ars Combinatoria"},{"key":"e_1_2_7_7_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-39.1.12"},{"key":"e_1_2_7_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2024.113962"},{"issue":"4","key":"e_1_2_7_9_1","first-page":"405","article-title":"Covering and Packing in Graphs. III: Cyclic and Acyclic Invariants","volume":"30","author":"Akiyama J.","year":"1980","journal-title":"Mathematica Slovaca"},{"key":"e_1_2_7_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-023-00024-9"},{"key":"e_1_2_7_11_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1998.1868"},{"key":"e_1_2_7_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2004.12.002"},{"key":"e_1_2_7_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2008.07.004"},{"key":"e_1_2_7_14_1","unstructured":"G.Kronenberg S.Letzter A.Pokrovskiy andL.Yepremyan \u201cDecomposing Cubic Graphs Into Isomorphic Linear Forests \u201darXiv preprint arXiv:2210.11458(2022)."},{"key":"e_1_2_7_15_1","first-page":"332","article-title":"Problem 13","volume":"23","author":"Wormald N.","year":"1987","journal-title":"Ars Combinatoria"},{"key":"e_1_2_7_16_1","doi-asserted-by":"publisher","DOI":"10.1017\/9781009036214.007"},{"key":"e_1_2_7_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(84)90101-X"},{"key":"e_1_2_7_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(84)90075-X"},{"key":"e_1_2_7_19_1","unstructured":"R.Jiang K.Jiang andM.Jiang \u201cDecomposing a Graph Into Subgraphs With Small Components \u201darXiv preprint arXiv:2110.00692(2021)."},{"key":"e_1_2_7_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792225297"},{"key":"e_1_2_7_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01202792"},{"key":"e_1_2_7_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(88)90068-8"},{"key":"e_1_2_7_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01889919"},{"key":"e_1_2_7_24_1","doi-asserted-by":"crossref","unstructured":"J.EdmondsandE. L.Johnson \u201cMatching: A Well\u2010Solved Class of Integer Linear Programs \u201d inCombinatorial Optimization\u2014Eureka You Shrink! Papers Dedicated to Jack Edmonds 5th International Workshop Aussois France March 5\u20139 2001 Revised Papers(Berlin Heidelberg:Springer 2003) 27\u201330.","DOI":"10.1007\/3-540-36478-1_3"},{"key":"e_1_2_7_25_1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1952-028-2"},{"key":"e_1_2_7_26_1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1954-033-3"},{"key":"e_1_2_7_27_1","doi-asserted-by":"crossref","unstructured":"L.Lov\u00e1szandM. D.Plummer Matching Theory Vol.367(American Mathematical Society 2009).","DOI":"10.1090\/chel\/367"},{"key":"e_1_2_7_28_1","doi-asserted-by":"crossref","unstructured":"S.BonduelleandF.Kardo\u0161 \u201cSubcubic Planar Graphs of Girth 7 Are Class I \u201dDiscrete Mathematics345 no.10(2022):113002.","DOI":"10.1016\/j.disc.2022.113002"},{"key":"e_1_2_7_29_1","unstructured":"H.Kronk M.Radlowski andB.Franen \u201cOn the Line Chromatic Number of Triangle\u2010Free Graphs \u201d inAbstract in Graph Theory Newsletter Vol.3(1974)."},{"key":"e_1_2_7_30_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22995"}],"container-title":["Journal of Graph Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/jgt.23208","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,13]],"date-time":"2025-03-13T17:18:55Z","timestamp":1741886335000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/jgt.23208"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,8]]},"references-count":29,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,5]]}},"alternative-id":["10.1002\/jgt.23208"],"URL":"https:\/\/doi.org\/10.1002\/jgt.23208","archive":["Portico"],"relation":{},"ISSN":["0364-9024","1097-0118"],"issn-type":[{"type":"print","value":"0364-9024"},{"type":"electronic","value":"1097-0118"}],"subject":[],"published":{"date-parts":[[2025,1,8]]},"assertion":[{"value":"2023-04-30","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-11-06","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-01-08","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}