3049 2022 eng 8 345 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.112903 true {"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,12,24]],"date-time":"2022-12-24T06:48:21Z","timestamp":1671864501451},"reference-count":32,"publisher":"Elsevier BV","issue":"8","license":[{"start":{"date-parts":[[2022,8,1]],"date-time":"2022-08-01T00:00:00Z","timestamp":1659312000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2022,8,1]],"date-time":"2022-08-01T00:00:00Z","timestamp":1659312000000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-017"},{"start":{"date-parts":[[2022,8,1]],"date-time":"2022-08-01T00:00:00Z","timestamp":1659312000000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-037"},{"start":{"date-parts":[[2022,8,1]],"date-time":"2022-08-01T00:00:00Z","timestamp":1659312000000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-012"},{"start":{"date-parts":[[2022,8,1]],"date-time":"2022-08-01T00:00:00Z","timestamp":1659312000000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-029"},{"start":{"date-parts":[[2022,8,1]],"date-time":"2022-08-01T00:00:00Z","timestamp":1659312000000},"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":[[2022,8]]},"DOI":"10.1016\/j.disc.2022.112903","type":"journal-article","created":{"date-parts":[[2022,3,31]],"date-time":"2022-03-31T11:11:59Z","timestamp":1648725119000},"page":"112903","update-policy":"http:\/\/dx.doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":0,"title":["Point partition numbers: Decomposable and indecomposable critical graphs"],"prefix":"10.1016","volume":"345","author":[{"given":"Justus","family":"von Postel","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.112903_br0010","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1112\/jlms\/s2-12.1.97","article-title":"Point arboricity critical graphs exists","volume":"12","author":"Bollob\u00e1s","year":"1975","journal-title":"J. Lond. Math. Soc."},{"key":"10.1016\/j.disc.2022.112903_br0020","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.112903_br0030","first-page":"3","article-title":"On decomposition of graphs into degenerate subgraphs","volume":"28","author":"Borodin","year":"1976","journal-title":"Metody Diskret. Anal."},{"key":"10.1016\/j.disc.2022.112903_br0040","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.112903_br0050","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."},{"key":"10.1016\/j.disc.2022.112903_br0060","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1112\/jlms\/s1-27.1.85","article-title":"A property of 4-chromatic graphs and some remarks on critical graphs","volume":"27","author":"Dirac","year":"1952","journal-title":"J. Lond. Math. Soc."},{"key":"10.1016\/j.disc.2022.112903_br0070","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.112903_br0080","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":"7","author":"Dirac","year":"1957","journal-title":"Proc. Lond. Math. Soc."},{"key":"10.1016\/j.disc.2022.112903_br0090","first-page":"43","article-title":"On the structure of 5- and 6-chromatic graphs","volume":"214\/215","author":"Dirac","year":"1974","journal-title":"J. Reine Angew. Math."},{"key":"10.1016\/j.disc.2022.112903_br0100","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.112903_br0110","first-page":"165","article-title":"Kritische Graphen I","volume":"8","author":"Gallai","year":"1963","journal-title":"Publ. Math. Inst. Hung. Acad. Sci."},{"key":"10.1016\/j.disc.2022.112903_br0120","first-page":"373","article-title":"Kritische Graphen II","volume":"8","author":"Gallai","year":"1963","journal-title":"Publ. Math. Inst. Hung. Acad. Sci."},{"key":"10.1016\/j.disc.2022.112903_br0130","first-page":"109","article-title":"Ein Dreifarbensatz f\u00fcr dreikreisfreie Netze auf der Kugel","volume":"8","author":"Gr\u00f6tzsch","year":"1958","journal-title":"Wiss. Z., Martin-Luther-Univ. Halle-Wittenb., Math.-Nat.wiss. Reihe"},{"key":"10.1016\/j.disc.2022.112903_br0140","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.112903_br0150","series-title":"Moore Sets, Graphs and Numbers","first-page":"175","article-title":"Color-critical graphs and hypergraphs with few edges: a survey","volume":"vol. 15","author":"Kostochka","year":"2006"},{"key":"10.1016\/j.disc.2022.112903_br0160","author":"Kostochka"},{"key":"10.1016\/j.disc.2022.112903_br0170","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.112903_br0180","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.112903_br0190","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.112903_br0200","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1002\/(SICI)1097-0118(199908)31:4<303::AID-JGT5>3.0.CO;2-G","article-title":"Chromatic neighborhood sets","volume":"31","author":"Molloy","year":"1999","journal-title":"J. Graph Theory"},{"key":"10.1016\/j.disc.2022.112903_br0210","first-page":"101","article-title":"On the structure of the point arboricity critical graphs","volume":"1","author":"Mih\u00f3k","year":"1981","journal-title":"Math. Slovaca"},{"key":"10.1016\/j.disc.2022.112903_br0220","series-title":"The Four Color Problem","author":"Ore","year":"1967"},{"key":"10.1016\/j.disc.2022.112903_br0230","article-title":"Point partition numbers: perfect graphs","volume":"38","author":"Postel","year":"2022","journal-title":"Graphs Comb."},{"key":"10.1016\/j.disc.2022.112903_br0240","author":"Postel"},{"key":"10.1016\/j.disc.2022.112903_br0250","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.112903_br0260","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.112903_br0270","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1002\/jgt.10010","article-title":"On the critical point-arboricity graphs","volume":"39","author":"\u0160krekovski","year":"2002","journal-title":"J. Graph Theory"},{"key":"10.1016\/j.disc.2022.112903_br0280","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/S0095-8956(03)00069-8","article-title":"Critical graphs with connected complements","volume":"89","author":"Stehl\u00edk","year":"2003","journal-title":"J. Comb. Theory, Ser. B"},{"key":"10.1016\/j.disc.2022.112903_br0290","unstructured":"M. Stiebitz, B. Toft, Gallai's decomposition result for critical graphs: an elementary proof, Manuscript, 2016."},{"key":"10.1016\/j.disc.2022.112903_br0300","first-page":"423","article-title":"Decomposable and indecomposable critical hypergraphs","volume":"7","author":"Stiebitz","year":"2016","journal-title":"J. Comb."},{"key":"10.1016\/j.disc.2022.112903_br0310","doi-asserted-by":"crossref","first-page":"254","DOI":"10.1016\/0095-8956(79)90017-0","article-title":"Critically partitionable graphs I","volume":"27","author":"Thomason","year":"1979","journal-title":"J. Comb. Theory, Ser. B"},{"key":"10.1016\/j.disc.2022.112903_br0320","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1016\/0012-365X(82)90083-8","article-title":"Critically partitionable graphs II","volume":"41","author":"Thomason","year":"1982","journal-title":"Discrete Math."}],"container-title":["Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0012365X22001091?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0012365X22001091?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2022,12,23]],"date-time":"2022-12-23T04:27:29Z","timestamp":1671769649000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0012365X22001091"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8]]},"references-count":32,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2022,8]]}},"alternative-id":["S0012365X22001091"],"URL":"https:\/\/doi.org\/10.1016\/j.disc.2022.112903","relation":{},"ISSN":["0012-365X"],"issn-type":[{"value":"0012-365X","type":"print"}],"subject":[],"published":{"date-parts":[[2022,8]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"Point partition numbers: Decomposable and indecomposable critical graphs","name":"articletitle","label":"Article Title"},{"value":"Discrete Mathematics","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/j.disc.2022.112903","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":"112903"}} 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 Justus von Postel Thomas Schweser Michael Stiebitz