{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,8,26]],"date-time":"2023-08-26T13:12:20Z","timestamp":1693055540864},"reference-count":28,"publisher":"Wiley","issue":"4","license":[{"start":{"date-parts":[[2021,10,11]],"date-time":"2021-10-11T00:00:00Z","timestamp":1633910400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"funder":[{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR DIGRAPHS ANR\u201019\u2010CE48\u20100013\u201001"],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["Journal of Graph Theory"],"published-print":{"date-parts":[[2022,4]]},"abstract":"Abstract<\/jats:title>Generalizing well\u2010known results of Erd\u0151s and Lov\u00e1sz, we show that every graph contains a spanning \u2010partite subgraph with , where is the edge\u2010connectivity of . In particular, together with a well\u2010known result due to Nash\u2010Williams and Tutte, this implies that every 7\u2010edge\u2010connected graph\u00a0contains a spanning bipartite graph whose edge set decomposes into two edge\u2010disjoint spanning trees. We show that this is best possible as it does not hold for infinitely many 6\u2010edge\u2010connected graphs. For directed graphs, it was shown by Bang\u2010Jensen et al. that there is no such that every \u2010arc\u2010connected digraph has a spanning strong bipartite subdigraph. We prove that every strong digraph has a spanning strong 3\u2010partite subdigraph and that every strong semicomplete digraph on at least six vertices contains a spanning strong bipartite subdigraph. We generalize this result to higher connectivities by proving that, for every positive integer , every \u2010arc\u2010connected digraph contains a spanning ()\u2010partite subdigraph which is \u2010arc\u2010connected and this is best possible. A conjecture by\u00a0Kreutzer et al.\u00a0implies that every digraph of minimum out\u2010degree contains a spanning 3\u2010partite subdigraph with minimum out\u2010degree at least . We prove that the bound would be best possible by providing an infinite class of digraphs with minimum out\u2010degree which do not contain any spanning 3\u2010partite subdigraph in which all out\u2010degrees are at least . We also prove that every digraph of minimum semidegree at least contains a spanning 6\u2010partite subdigraph in which every vertex has in\u2010 and out\u2010degree at least .<\/jats:p>","DOI":"10.1002\/jgt.22755","type":"journal-article","created":{"date-parts":[[2021,10,13]],"date-time":"2021-10-13T03:32:00Z","timestamp":1634095920000},"page":"615-636","update-policy":"http:\/\/dx.doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Low chromatic spanning sub(di)graphs with prescribed degree or connectivity properties"],"prefix":"10.1002","volume":"99","author":[{"ORCID":"http:\/\/orcid.org\/0000-0001-5783-7125","authenticated-orcid":false,"given":"J.","family":"Bang\u2010Jensen","sequence":"first","affiliation":[{"name":"Department of Mathematics and Computer Science University of Southern Denmark Odense Denmark"}]},{"ORCID":"http:\/\/orcid.org\/0000-0002-3447-8112","authenticated-orcid":false,"given":"F.","family":"Havet","sequence":"additional","affiliation":[{"name":"CNRS Universit\u00e9 C\u00f4te d'Azur I3S and INRIA Sophia Antipolis France"}]},{"given":"M.","family":"Kriesell","sequence":"additional","affiliation":[{"name":"Department of Mathematics Technische Universit\u00e4t Ilmenau Ilmenau Germany"}]},{"given":"A.","family":"Yeo","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Computer Science University of Southern Denmark Odense Denmark"},{"name":"Department of Mathematics University of Johannesburg Auckland Park Johannesburg South Africa"}]}],"member":"311","published-online":{"date-parts":[[2021,10,11]]},"reference":[{"key":"e_1_2_10_2_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548306008042"},{"key":"e_1_2_10_3_1","first-page":"7","article-title":"The wonderful Walecki construction","volume":"52","author":"Alspach B.","year":"2008","journal-title":"Bull. Inst. Combin. Appl"},{"key":"e_1_2_10_4_1","first-page":"259","article-title":"Extremal k\u2010colourable subgraphs","volume":"16","author":"Andersen L. D.","year":"1983","journal-title":"Ars Combin"},{"key":"e_1_2_10_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1992.267823"},{"key":"e_1_2_10_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2017.11.007"},{"key":"e_1_2_10_7_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22444"},{"key":"e_1_2_10_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-84800-998-1"},{"key":"e_1_2_10_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2004.10.002"},{"key":"e_1_2_10_10_1","first-page":"2151","article-title":"Chemins et circuits hamiltoniens des graphes complets","volume":"249","author":"Camion P.","year":"1959","journal-title":"C. R. Acad. Sci. Paris"},{"key":"e_1_2_10_11_1","first-page":"91","volume-title":"Combinatorial Algorithms","author":"Edmonds J.","year":"1973"},{"key":"e_1_2_10_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02760037"},{"key":"e_1_2_10_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01788546"},{"key":"e_1_2_10_14_1","unstructured":"1979 W. H. Freeman San Francisco M. R. Garey D. S. Johnson Computers and intractability"},{"key":"e_1_2_10_15_1","doi-asserted-by":"publisher","DOI":"10.1017\/S096354831700044X"},{"key":"e_1_2_10_16_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199608\/09)9:1\/2<163::AID-RSA10>3.0.CO;2-P"},{"key":"e_1_2_10_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1006611"},{"key":"e_1_2_10_18_1","doi-asserted-by":"publisher","DOI":"10.37236\/6762"},{"key":"e_1_2_10_19_1","doi-asserted-by":"publisher","DOI":"10.37236\/6410"},{"key":"e_1_2_10_20_1","first-page":"237","article-title":"On decompositions of graphs","volume":"1","author":"Lov\u00e1sz L.","year":"1966","journal-title":"Stud. Sci. Math. Hung."},{"key":"e_1_2_10_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01238648"},{"key":"e_1_2_10_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(82)80009-7"},{"key":"e_1_2_10_23_1","doi-asserted-by":"publisher","DOI":"10.4153\/CMB-1966-038-7"},{"key":"e_1_2_10_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/0405004"},{"key":"e_1_2_10_25_1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1960-049-6"},{"key":"e_1_2_10_26_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-36.1.445"},{"key":"e_1_2_10_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(80)90061-1"},{"key":"e_1_2_10_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(85)80025-1"},{"key":"e_1_2_10_29_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-36.1.221"}],"container-title":["Journal of Graph Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/jgt.22755","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/full-xml\/10.1002\/jgt.22755","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/jgt.22755","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,26]],"date-time":"2023-08-26T00:04:31Z","timestamp":1693008271000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/jgt.22755"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10,11]]},"references-count":28,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,4]]}},"alternative-id":["10.1002\/jgt.22755"],"URL":"https:\/\/doi.org\/10.1002\/jgt.22755","archive":["Portico"],"relation":{},"ISSN":["0364-9024","1097-0118"],"issn-type":[{"value":"0364-9024","type":"print"},{"value":"1097-0118","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,10,11]]},"assertion":[{"value":"2021-09-20","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-09-22","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-10-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}