3054 2020 eng 7 33 27 1 96 article Wiley 0 -- 2025-07-16 -- The paper deals with partitions of hypergraphs into induced subhypergraphs satisfying constraints on their degeneracy. Our hypergraphs may have multiple edges, but no loops. Given a hypergraph and a sequence of vertex functions such that for all , we want to find a sequence of vertex disjoint induced subhypergraphs containing all vertices of such that each hypergraph is strictly ‐degenerate, that is, for every nonempty subhypergraph there is a vertex such that . Our main result in this paper says that such a sequence of hypergraphs exists if and only if is not a so‐called hard pair. Hard pairs form a recursively defined family of configurations, obtained from three basic types of configurations by the operation of merging a vertex. Our main result has several interesting applications related to generalized hypergraph coloring problems. Journal of Graph Theory 0364-9024 https://doi.org/10.1002/jgt.22575 true {"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T02:16:19Z","timestamp":1740104179742,"version":"3.37.3"},"reference-count":21,"publisher":"Wiley","issue":"1","license":[{"start":{"date-parts":[[2020,5,5]],"date-time":"2020-05-05T00:00:00Z","timestamp":1588636800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001655","name":"Deutscher Akademischer Austauschdienst","doi-asserted-by":"publisher","award":["57320575"],"id":[{"id":"10.13039\/501100001655","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":[[2021,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The paper deals with partitions of hypergraphs into induced subhypergraphs satisfying constraints on their degeneracy. Our hypergraphs may have multiple edges, but no loops. Given a hypergraph and a sequence of vertex functions such that for all , we want to find a sequence of vertex disjoint induced subhypergraphs containing all vertices of such that each hypergraph is strictly \u2010degenerate, that is, for every nonempty subhypergraph there is a vertex such that . Our main result in this paper says that such a sequence of hypergraphs exists if and only if is not a so\u2010called hard pair. Hard pairs form a recursively defined family of configurations, obtained from three basic types of configurations by the operation of merging a vertex. Our main result has several interesting applications related to generalized hypergraph coloring problems.<\/jats:p>","DOI":"10.1002\/jgt.22575","type":"journal-article","created":{"date-parts":[[2020,5,6]],"date-time":"2020-05-06T02:56:52Z","timestamp":1588733812000},"page":"7-33","update-policy":"https:\/\/doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Partitions of hypergraphs under variable degeneracy constraints"],"prefix":"10.1002","volume":"96","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4969-7115","authenticated-orcid":false,"given":"Thomas","family":"Schweser","sequence":"first","affiliation":[{"name":"Institute of Mathematics Technische Universit\u00e4t Ilmenau Ilmenau Germany"}]},{"given":"Michael","family":"Stiebitz","sequence":"additional","affiliation":[{"name":"Institute of Mathematics Technische Universit\u00e4t Ilmenau Ilmenau Germany"}]}],"member":"311","published-online":{"date-parts":[[2020,5,5]]},"reference":[{"issue":"2020","key":"e_1_2_6_2_1","first-page":"103015","article-title":"Partitioning a graph into degenerate subgraphs","volume":"83","author":"Abu\u2010Khzam F. N.","journal-title":"Eur. J. Combinator."},{"key":"e_1_2_6_3_1","doi-asserted-by":"publisher","DOI":"10.1112\/blms\/11.2.113"},{"key":"e_1_2_6_4_1","first-page":"3","article-title":"On decomposition of graphs into degenerate subgraphs","volume":"28","author":"Borodin O. V.","year":"1976","journal-title":"Metody Diskret. Analiz"},{"key":"e_1_2_6_5_1","unstructured":"O. V.Borodin Problems of colouring and of covering the vertex set of a graph by induced subgraphs Ph.D.Thesis Novosibirsk(in Russian) 1979."},{"key":"e_1_2_6_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(99)00221-6"},{"key":"e_1_2_6_7_1","doi-asserted-by":"publisher","DOI":"10.1017\/S030500410002168X"},{"key":"e_1_2_6_8_1","first-page":"125","article-title":"Choosability in graphs","author":"Erd\u00f6s P.","year":"1979","journal-title":"Congr. Numer."},{"key":"e_1_2_6_9_1","doi-asserted-by":"publisher","DOI":"10.1002\/mana.19690390415"},{"key":"e_1_2_6_10_1","first-page":"379","volume-title":"Proc. 5th British Combinatorial Conf","author":"Jones R. P.","year":"1975"},{"key":"e_1_2_6_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(95)00294-7"},{"key":"e_1_2_6_12_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s2-9.3.459"},{"key":"e_1_2_6_13_1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1970-125-1"},{"key":"e_1_2_6_14_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s2-4.4.577"},{"key":"e_1_2_6_15_1","first-page":"237","article-title":"On decomposition of graphs","volume":"1","author":"Lov\u00e1sz L.","year":"1966","journal-title":"Studia Sci. Math. Hungar."},{"key":"e_1_2_6_16_1","first-page":"481","article-title":"A min\u2010max theorem for graphs with application to graph coloring","volume":"10","author":"Matula D. W.","year":"1968","journal-title":"SIAM Rev."},{"key":"e_1_2_6_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(77)90162-5"},{"journal-title":"Discuss. Math. Graph Theory.","article-title":"Generalized hypergraph coloring","author":"Schweser T.","key":"e_1_2_6_18_1"},{"key":"e_1_2_6_19_1","unstructured":"T.SchweserandM.Stiebitz Vertex partition of hypergraphs and maximum degenerate subhypergraphs. arxiv: 1807.02308 (2018)."},{"key":"e_1_2_6_20_1","first-page":"3","article-title":"Vertex coloring with given colors","volume":"29","author":"Vizing V. G.","year":"1976","journal-title":"Diskret. Analiz."},{"key":"e_1_2_6_21_1","first-page":"1","article-title":"Partition a graph into two induced forests","volume":"29","author":"Wu Y.","year":"1996","journal-title":"J. Math. Study."},{"key":"e_1_2_6_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2005.09.016"}],"container-title":["Journal of Graph Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/jgt.22575","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/full-xml\/10.1002\/jgt.22575","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/jgt.22575","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,4]],"date-time":"2023-09-04T17:12:27Z","timestamp":1693847547000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/jgt.22575"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,5,5]]},"references-count":21,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["10.1002\/jgt.22575"],"URL":"https:\/\/doi.org\/10.1002\/jgt.22575","archive":["Portico"],"relation":{},"ISSN":["0364-9024","1097-0118"],"issn-type":[{"type":"print","value":"0364-9024"},{"type":"electronic","value":"1097-0118"}],"subject":[],"published":{"date-parts":[[2020,5,5]]},"assertion":[{"value":"2018-04-20","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-04-18","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-05-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}} journal-article http://creativecommons.org/licenses/by-nc-nd/4.0/ crossref PersonAuthorFirstName_1,PersonAuthorLastName_1,PersonAuthorIdentifierOrcid_1,PersonAuthorFirstName_2,PersonAuthorLastName_2,PublisherName,TitleMain_1,Language,TitleAbstract_1,TitleParent_1,PageNumber,PageFirst,PageLast,Issue,Volume,CompletedYear,IdentifierIssn,Enrichmentlocal_crossrefLicence doi-import 2 Thomas Schweser Michael Stiebitz