3048 2023 eng 20 11 346 article Elsevier BV 0 -- 2025-07-16 -- In the present paper we extend the following three coloring concepts for the class of finite undirected graphs having multiple edges but no loops. First of all, the generalized coloring concept, in which the same colored vertices of a graph induce a subgraph satisfying a prescribed graph property. Secondly, the concept of variable degeneracy, which was introduced by Borodin, Kostochka and Toft in 2000; this makes it possible to give a common generalization of the point partition number and the list chromatic number. Finally, the DP-coloring concept as introduced by Ďvorák and Postle in 2018, where a list assignment of a graph is replaced by a cover. Combining these three coloring concepts leads to generalizations of various classical coloring results, including the theorems of Brooks, of Gallai, and of Erdős, Rubin and Taylor. Our main result is a DP-version of a theorem about partitions of graphs into a fixed number of induced subgraphs with bounded variable degeneracy due to Borodin, Kostochka, and Toft. Discrete Mathematics 0012-365X 10.1016/j.disc.2022.113186 true {"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,6,1]],"date-time":"2024-06-01T00:13:00Z","timestamp":1717200780814},"reference-count":40,"publisher":"Elsevier BV","issue":"11","license":[{"start":{"date-parts":[[2023,11,1]],"date-time":"2023-11-01T00:00:00Z","timestamp":1698796800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2023,11,1]],"date-time":"2023-11-01T00:00:00Z","timestamp":1698796800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"},{"start":{"date-parts":[[2025,8,28]],"date-time":"2025-08-28T00:00:00Z","timestamp":1756339200000},"content-version":"am","delay-in-days":666,"URL":"http:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"},{"start":{"date-parts":[[2023,11,1]],"date-time":"2023-11-01T00:00:00Z","timestamp":1698796800000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-017"},{"start":{"date-parts":[[2023,11,1]],"date-time":"2023-11-01T00:00:00Z","timestamp":1698796800000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-037"},{"start":{"date-parts":[[2023,11,1]],"date-time":"2023-11-01T00:00:00Z","timestamp":1698796800000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-012"},{"start":{"date-parts":[[2023,11,1]],"date-time":"2023-11-01T00:00:00Z","timestamp":1698796800000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-029"},{"start":{"date-parts":[[2023,11,1]],"date-time":"2023-11-01T00:00:00Z","timestamp":1698796800000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-004"}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Discrete Mathematics"],"published-print":{"date-parts":[[2023,11]]},"DOI":"10.1016\/j.disc.2022.113186","type":"journal-article","created":{"date-parts":[[2022,9,28]],"date-time":"2022-09-28T12:27:50Z","timestamp":1664368070000},"page":"113186","update-policy":"http:\/\/dx.doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":0,"title":["Generalized DP-colorings of graphs"],"prefix":"10.1016","volume":"346","author":[{"given":"Alexandr V.","family":"Kostochka","sequence":"first","affiliation":[]},{"given":"Thomas","family":"Schweser","sequence":"additional","affiliation":[]},{"given":"Michael","family":"Stiebitz","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/j.disc.2022.113186_br0010","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1016\/0012-365X(89)90196-9","article-title":"The subchromatic number of a graph","volume":"74","author":"Albertson","year":"1989","journal-title":"Discrete Math."},{"key":"10.1016\/j.disc.2022.113186_br0020","doi-asserted-by":"crossref","first-page":"521","DOI":"10.1002\/jgt.22227","article-title":"Sharp Dirac's theorem for DP-critical graphs","volume":"88","author":"Bernsteyn","year":"2018","journal-title":"J. Graph Theory"},{"key":"10.1016\/j.disc.2022.113186_br0030","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1134\/S0037446617010049","article-title":"On DP-coloring of graphs and multigraphs","volume":"58","author":"Bernshteyn","year":"2017","journal-title":"Sib. Math. J."},{"key":"10.1016\/j.disc.2022.113186_br0040","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1112\/blms\/11.2.113","article-title":"Optimal vertex partition","volume":"11","author":"Bollob\u00e1s","year":"1979","journal-title":"Bull. Lond. Math. Soc."},{"key":"10.1016\/j.disc.2022.113186_br0050","first-page":"3","article-title":"On decomposition of graphs into degenerate subgraphs","volume":"28","author":"Borodin","year":"1976","journal-title":"Metody Diskret. Analiz."},{"key":"10.1016\/j.disc.2022.113186_br0060","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1016\/S0012-365X(99)00221-6","article-title":"Variable degeneracy: extensions of Brooks' and Gallai's theorems","volume":"214","author":"Borodin","year":"2000","journal-title":"Discrete Math."},{"key":"10.1016\/j.disc.2022.113186_br0070","doi-asserted-by":"crossref","first-page":"5","DOI":"10.7151\/dmgt.1037","article-title":"A survey of hereditary properties of graphs","volume":"17","author":"Borowiecki","year":"1997","journal-title":"Discuss. Math., Graph Theory"},{"key":"10.1016\/j.disc.2022.113186_br0080","doi-asserted-by":"crossref","first-page":"185","DOI":"10.7151\/dmgt.1016","article-title":"Generalized list colouring of graphs","volume":"15","author":"Borowiecki","year":"1995","journal-title":"Discuss. Math., Graph Theory"},{"key":"10.1016\/j.disc.2022.113186_br0090","series-title":"Advances in Graph Theory","first-page":"41","article-title":"Hereditary properties of graphs","author":"Borowiecki","year":"1991"},{"key":"10.1016\/j.disc.2022.113186_br0100","doi-asserted-by":"crossref","first-page":"194","DOI":"10.1017\/S030500410002168X","article-title":"On colouring the nodes of a network","volume":"37","author":"Brooks","year":"1941","journal-title":"Proc. Camb. Philos. Soc., Math. Phys. Sci."},{"key":"10.1016\/j.disc.2022.113186_br0110","doi-asserted-by":"crossref","first-page":"42","DOI":"10.4064\/fm-40-1-42-55","article-title":"The structure of k-chromatic graphs","volume":"40","author":"Dirac","year":"1953","journal-title":"Fundam. Math."},{"key":"10.1016\/j.disc.2022.113186_br0120","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1112\/plms\/s3-7.1.161","article-title":"A theorem of R. L: Brooks and a conjecture of H. Hadwiger","volume":"3","author":"Dirac","year":"1957","journal-title":"Proc. Lond. Math. Soc."},{"key":"10.1016\/j.disc.2022.113186_br0130","first-page":"150","article-title":"The number of edges in critical graphs","volume":"268\/269","author":"Dirac","year":"1974","journal-title":"J. Reine Angew. Math."},{"key":"10.1016\/j.disc.2022.113186_br0140","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1016\/j.jctb.2017.09.001","article-title":"Correspondence coloring and its application to list-coloring planar graphs without cycles of length 4 to 8","volume":"129","author":"\u010evor\u00e1k","year":"2018","journal-title":"J. Comb. Theory, Ser. B"},{"key":"10.1016\/j.disc.2022.113186_br0150","first-page":"125","article-title":"Choosability in graphs","volume":"XXVI","author":"Erd\u0151s","year":"1979","journal-title":"Congr. Numer."},{"key":"10.1016\/j.disc.2022.113186_br0160","first-page":"165","article-title":"Kritische Graphen I","volume":"8","author":"Gallai","year":"1963","journal-title":"Publ. Math. Inst. Hungar. Acad. Sci."},{"key":"10.1016\/j.disc.2022.113186_br0170","doi-asserted-by":"crossref","first-page":"1823","DOI":"10.1016\/j.disc.2012.01.028","article-title":"Two results on the digraph chromatic number","volume":"312","author":"Harutyunyan","year":"2012","journal-title":"Discrete Math."},{"key":"10.1016\/j.disc.2022.113186_br0180","doi-asserted-by":"crossref","first-page":"203","DOI":"10.4153\/CMB-1968-023-5","article-title":"On partitioning planar graphs","volume":"11","author":"Hedetniemi","year":"1968","journal-title":"Can. Math. Bull."},{"key":"10.1016\/j.disc.2022.113186_br0190","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1016\/j.jctb.2019.05.004","article-title":"Improved lower bound on the number of edges in list critical and online list critical graphs","volume":"140","author":"Kierstead","year":"2020","journal-title":"J. Comb. Theory, Ser. B"},{"key":"10.1016\/j.disc.2022.113186_br0200","doi-asserted-by":"crossref","first-page":"148","DOI":"10.1002\/jgt.22425","article-title":"A note on a Brooks' type theorem for DP-coloring","volume":"91","author":"Kim","year":"2019","journal-title":"J. Graph Theory"},{"key":"10.1016\/j.disc.2022.113186_br0210","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1002\/jgt.998","article-title":"A list version of Dirac's theorem on the number of edges in colour-critical graphs","volume":"39","author":"Kostochka","year":"2002","journal-title":"J. Graph Theory"},{"key":"10.1016\/j.disc.2022.113186_br0220","doi-asserted-by":"crossref","first-page":"374","DOI":"10.1016\/S0095-8956(02)00035-7","article-title":"A new lower bound on the number of edges in colour-critical graphs and hypergraphs","volume":"87","author":"Kostochka","year":"2003","journal-title":"J. Comb. Theory, Ser. B"},{"key":"10.1016\/j.disc.2022.113186_br0230","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1016\/S0012-365X(98)00100-9","article-title":"The colour theorems of Brooks and Gallai extended","volume":"191","author":"Kostochka","year":"1996","journal-title":"Discrete Math."},{"key":"10.1016\/j.disc.2022.113186_br0240","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1016\/j.jctb.2014.05.002","article-title":"Ore's conjecture on color-critical graphs is almost true","volume":"109","author":"Kostochka","year":"2014","journal-title":"J. Comb. Theory, Ser. B"},{"key":"10.1016\/j.disc.2022.113186_br0250","doi-asserted-by":"crossref","first-page":"459","DOI":"10.1112\/jlms\/s2-9.3.459","article-title":"Critical point-arboritic graphs","volume":"9","author":"Kronk","year":"1975","journal-title":"J. Lond. Math. Soc."},{"key":"10.1016\/j.disc.2022.113186_br0260","doi-asserted-by":"crossref","first-page":"1082","DOI":"10.4153\/CJM-1970-125-1","article-title":"k-degenerate graphs","volume":"22","author":"Lick","year":"1970","journal-title":"Can. J. Math."},{"key":"10.1016\/j.disc.2022.113186_br0270","first-page":"237","article-title":"On decomposition of graphs","volume":"1","author":"Lov\u00e1sz","year":"1966","journal-title":"Studia Sci. Math. Hung."},{"key":"10.1016\/j.disc.2022.113186_br0280","author":"Lu"},{"key":"10.1016\/j.disc.2022.113186_br0290","doi-asserted-by":"crossref","first-page":"167","DOI":"10.7151\/dmgt.1141","article-title":"Gallai's inequality for critical graphs of reducible hereditary properties","volume":"21","author":"Mih\u00f3k","year":"2001","journal-title":"Discuss. Math., Graph Theory"},{"key":"10.1016\/j.disc.2022.113186_br0300","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1016\/0012-365X(77)90162-5","article-title":"An extension of Brooks' theorem to n-degenerate graphs","volume":"17","author":"Mitchem","year":"1977","journal-title":"Discrete Math."},{"key":"10.1016\/j.disc.2022.113186_br0310","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1002\/jgt.21634","article-title":"Destroying noncomplete regular components in graph partitions","volume":"72","author":"Rabern","year":"2013","journal-title":"J. Graph Theory"},{"key":"10.1016\/j.disc.2022.113186_br0320","doi-asserted-by":"crossref","first-page":"1028","DOI":"10.1016\/j.disc.2013.01.007","article-title":"Partitioning and coloring graphs with degree constraints","volume":"313","author":"Rabern","year":"2013","journal-title":"Discrete Math."},{"key":"10.1016\/j.disc.2022.113186_br0330","doi-asserted-by":"crossref","first-page":"103","DOI":"10.7151\/dmgt.2168","article-title":"Generalized hypergraph coloring","volume":"41","author":"Schweser","year":"2021","journal-title":"Discuss. Math., Graph Theory"},{"key":"10.1016\/j.disc.2022.113186_br0340","doi-asserted-by":"crossref","first-page":"196","DOI":"10.1016\/j.tcs.2019.09.010","article-title":"DP-degree colorable hypergraphs","volume":"796","author":"Schweser","year":"2019","journal-title":"Theor. Comput. Sci."},{"key":"10.1016\/j.disc.2022.113186_br0350","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1002\/jgt.22575","article-title":"Partition of hypergraphs under variable degeneracy constraints","volume":"96","author":"Schweser","year":"2021","journal-title":"J. Graph Theory"},{"key":"10.1016\/j.disc.2022.113186_br0360","doi-asserted-by":"crossref","first-page":"89","DOI":"10.7151\/dmgt.2238","article-title":"Analogue of DP-coloring on variable degeneracy and its applications on list vertex-arboricity and DP-coloring","volume":"42","author":"Sittitrai","year":"2022","journal-title":"Discuss. Math., Graph Theory"},{"key":"10.1016\/j.disc.2022.113186_br0370","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1002\/jgt.10010","article-title":"On the critical point-aboricity graphs","volume":"39","author":"\u0160krekovski","year":"2002","journal-title":"J. Graph Theory"},{"key":"10.1016\/j.disc.2022.113186_br0380","doi-asserted-by":"crossref","first-page":"4931","DOI":"10.1016\/j.disc.2008.05.021","article-title":"On list critical graphs","volume":"309","author":"Stiebitz","year":"2009","journal-title":"Discrete Math."},{"key":"10.1016\/j.disc.2022.113186_br0390","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1006\/jctb.1996.1722","article-title":"Color-critical graphs on a fixed surface","volume":"70","author":"Thomassen","year":"1997","journal-title":"J. Comb. Theory, Ser. B"},{"key":"10.1016\/j.disc.2022.113186_br0400","first-page":"3","article-title":"Vertex coloring with given colors","volume":"29","author":"Vizing","year":"1976","journal-title":"Diskretn. Anal."}],"container-title":["Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0012365X22003922?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0012365X22003922?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2024,5,31]],"date-time":"2024-05-31T15:52:15Z","timestamp":1717170735000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0012365X22003922"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11]]},"references-count":40,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2023,11]]}},"alternative-id":["S0012365X22003922"],"URL":"https:\/\/doi.org\/10.1016\/j.disc.2022.113186","relation":{},"ISSN":["0012-365X"],"issn-type":[{"value":"0012-365X","type":"print"}],"subject":[],"published":{"date-parts":[[2023,11]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"Generalized DP-colorings of graphs","name":"articletitle","label":"Article Title"},{"value":"Discrete Mathematics","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/j.disc.2022.113186","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"article","name":"content_type","label":"Content Type"},{"value":"\u00a9 2022 Elsevier B.V. All rights reserved.","name":"copyright","label":"Copyright"}],"article-number":"113186"}} journal-article https://www.elsevier.com/tdm/userlicense/1.0/ crossref PersonAuthorFirstName_1,PersonAuthorLastName_1,PersonAuthorFirstName_2,PersonAuthorLastName_2,PersonAuthorFirstName_3,PersonAuthorLastName_3,PublisherName,TitleMain_1,Language,TitleParent_1,ArticleNumber,Issue,Volume,CompletedYear,IdentifierIssn,Enrichmentlocal_crossrefLicence doi-import false false 2 Alexandr V. Kostochka Thomas Schweser Michael Stiebitz