{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,11]],"date-time":"2026-04-11T01:52:50Z","timestamp":1775872370876,"version":"3.50.1"},"reference-count":14,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2024,11,22]],"date-time":"2024-11-22T00:00:00Z","timestamp":1732233600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,11,22]],"date-time":"2024-11-22T00:00:00Z","timestamp":1732233600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100019180","name":"HORIZON EUROPE European Research Council","doi-asserted-by":"publisher","award":["ERMiD"],"award-info":[{"award-number":["ERMiD"]}],"id":[{"id":"10.13039\/100019180","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003825","name":"Magyar Tudom\u00e1nyos Akad\u00e9mia","doi-asserted-by":"publisher","award":["J\u00e1nos Bolyai Research Scholarship"],"award-info":[{"award-number":["J\u00e1nos Bolyai Research Scholarship"]}],"id":[{"id":"10.13039\/501100003825","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100011019","name":"Nemzeti Kutat\u00e1si Fejleszt\u00e9si \u00e9s Innov\u00e1ci\u00f3s Hivatal","doi-asserted-by":"publisher","award":["TKP2021-NKTA-62"],"award-info":[{"award-number":["TKP2021-NKTA-62"]}],"id":[{"id":"10.13039\/501100011019","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100011019","name":"Nemzeti Kutat\u00e1si Fejleszt\u00e9si \u00e9s Innov\u00e1ci\u00f3s Hivatal","doi-asserted-by":"publisher","award":["UNKP-22-5"],"award-info":[{"award-number":["UNKP-22-5"]}],"id":[{"id":"10.13039\/501100011019","id-type":"DOI","asserted-by":"publisher"}]},{"name":"HUN-REN Alfr\u00e9d R\u00e9nyi Institute of Mathematics"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Graphs and Combinatorics"],"published-print":{"date-parts":[[2024,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We exhibit a 5-uniform hypergraph that has no polychromatic 3-coloring, but all its restricted subhypergraphs with edges of size at least 3 are 2-colorable. This disproves a bold conjecture of Keszegh and the author, and can be considered as the first step to understand polychromatic colorings of hereditary hypergraph families better since the seminal work of Berge. We also show that our method cannot give hypergraphs of arbitrary high uniformity, and mention some connections to panchromatic colorings.<\/jats:p>","DOI":"10.1007\/s00373-024-02836-y","type":"journal-article","created":{"date-parts":[[2024,11,22]],"date-time":"2024-11-22T02:30:52Z","timestamp":1732242652000},"update-policy":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Note on Polychromatic Coloring of Hereditary Hypergraph Families"],"prefix":"10.1007","volume":"40","author":[{"ORCID":"https:\/\/2.zoppoz.workers.dev:443\/https\/orcid.org\/0000-0003-2970-0943","authenticated-orcid":false,"given":"D\u00f6m\u00f6t\u00f6r","family":"P\u00e1lv\u00f6lgyi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,11,22]]},"reference":[{"key":"2836_CR1","doi-asserted-by":"publisher","first-page":"2250","DOI":"10.1137\/19M1290231","volume":"34","author":"E Ackerman","year":"2020","unstructured":"Ackerman, E., Keszegh, B., P\u00e1lv\u00f6lgyi, D.: Coloring hypergraphs defined by stabbed pseudo-disks and ABAB-free hypergraphs. SIAM J. Discret. Math. 34, 2250\u20132269 (2020)","journal-title":"SIAM J. Discret. Math."},{"key":"2836_CR2","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1007\/BF01584535","volume":"2","author":"C Berge","year":"1972","unstructured":"Berge, C.: Balanced matrices. Math. Program. 2, 19\u201331 (1972)","journal-title":"Math. Program."},{"key":"2836_CR3","unstructured":"Bursics, B., Csonka, B., Szepessy, L.: Hitting sets and colorings of hypergraphs, preprint"},{"key":"2836_CR4","doi-asserted-by":"crossref","unstructured":"Cardinal, J., Knauer, K., Micek, P., Ueckerdt, D.. P\u00e1lv\u00f6lgyi., T., Varadarajan, N.: Colouring bottomless rectangles and arborescences. Comput. Geom.: Theory Appl. 115, 102020 (2023)","DOI":"10.1016\/j.comgeo.2023.102020"},{"key":"2836_CR5","doi-asserted-by":"crossref","unstructured":"Chekan, V., Ueckerdt, T.: Polychromatic Colorings of Unions of Geometric Hypergraphs, in Proceedings of Graph-Theoretic Concepts in Computer Science (WG 2022), LNCS 13453, Springer, Cham","DOI":"10.1007\/978-3-031-15914-5_11"},{"key":"2836_CR6","doi-asserted-by":"publisher","first-page":"1027","DOI":"10.1007\/s00493-021-4846-5","volume":"42","author":"G Dam\u00e1sdi","year":"2022","unstructured":"Dam\u00e1sdi, G., P\u00e1lv\u00f6lgyi, D.: Realizing an m-uniform four-chromatic hypergraph with disks. Combinatorica 42, 1027\u20131048 (2022)","journal-title":"Combinatorica"},{"key":"2836_CR7","unstructured":"Dam\u00e1sdi, G., P\u00e1lv\u00f6lgyi, D.: Three-chromatic geometric hypergraphs, to appear in Journal of the European Mathematical Society"},{"key":"2836_CR8","unstructured":"Erd\u0151s, P., Lov\u00e1sz, L.: Problems and results on $$3$$-chromatic hypergraphs and some related questions, in Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erd\u0151s on his 60th birthday), vol. II, 609\u2013627. Colloq. Math. Soc. J\u00e1nos Bolyai, 10, North-Holland, Amsterdam (1973)"},{"key":"2836_CR9","first-page":"1","volume":"10","author":"B Keszegh","year":"2019","unstructured":"Keszegh, B., P\u00e1lv\u00f6lgyi, D.: An abstract approach to polychromatic coloring: shallow hitting sets in ABA-free hypergraphs and pseudohalfplanes. J. Comput. Geom. 10, 1\u201326 (2019)","journal-title":"J. Comput. Geom."},{"key":"2836_CR10","doi-asserted-by":"publisher","first-page":"674","DOI":"10.1007\/s00454-019-00096-9","volume":"62","author":"B Keszegh","year":"2019","unstructured":"Keszegh, B., P\u00e1lv\u00f6lgyi, D.: Proper coloring of geometric hypergraphs. Discret. Comput. Geom. 62, 674\u2013689 (2019)","journal-title":"Discret. Comput. Geom."},{"key":"2836_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.37236\/1670","volume":"9","author":"A Kostochka","year":"2002","unstructured":"Kostochka, A.: On a theorem of Erd\u0151s, Rubin, and Taylor on choosability of complete bipartite graphs. Electron. J. Combin. 9, 1\u20134 (2002)","journal-title":"Electron. J. Combin."},{"key":"2836_CR12","first-page":"219","volume-title":"Geometry, Intuitive, Discrete, and Convex, Bolyai Society Mathematical Studies","author":"J Pach","year":"2014","unstructured":"Pach, J., P\u00e1lv\u00f6lgyi, D., T\u00f3th, G.: Survey on decomposition of multiple coverings. In: B\u00e1r\u00e1ny, I., B\u00f6r\u00f6czky, K.J., Fejes T\u00f3th, G., Pach, J. (eds.) Geometry, Intuitive, Discrete, and Convex, Bolyai Society Mathematical Studies, vol. 24, pp. 219\u2013257. Springer (2014)"},{"key":"2836_CR13","unstructured":"Planken, T., Ueckerdt, T.: Polychromatic Colorings of Geometric Hypergraphs via Shallow Hitting Sets, preprint"},{"key":"2836_CR14","doi-asserted-by":"publisher","first-page":"226","DOI":"10.1002\/jgt.20527","volume":"67","author":"D Shabanov","year":"2011","unstructured":"Shabanov, D.: On a generalization of Rubin\u2019s theorem. J. Graph. Theory 67, 226\u2013234 (2011)","journal-title":"J. Graph. Theory"}],"container-title":["Graphs and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/link.springer.com\/content\/pdf\/10.1007\/s00373-024-02836-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/link.springer.com\/article\/10.1007\/s00373-024-02836-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/link.springer.com\/content\/pdf\/10.1007\/s00373-024-02836-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,6]],"date-time":"2024-12-06T20:07:54Z","timestamp":1733515674000},"score":1,"resource":{"primary":{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/link.springer.com\/10.1007\/s00373-024-02836-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11,22]]},"references-count":14,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2024,12]]}},"alternative-id":["2836"],"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1007\/s00373-024-02836-y","relation":{},"ISSN":["0911-0119","1435-5914"],"issn-type":[{"value":"0911-0119","type":"print"},{"value":"1435-5914","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,11,22]]},"assertion":[{"value":"17 September 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 July 2024","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 August 2024","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 November 2024","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"131"}}