{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:22:02Z","timestamp":1740122522061,"version":"3.37.3"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"9","license":[{"start":{"date-parts":[[2021,3,25]],"date-time":"2021-03-25T00:00:00Z","timestamp":1616630400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,3,25]],"date-time":"2021-03-25T00:00:00Z","timestamp":1616630400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003825","name":"Magyar Tudom\u00e1nyos Akad\u00e9mia","doi-asserted-by":"publisher","award":["J\u00e1nos Bolyai Scholarship"],"award-info":[{"award-number":["J\u00e1nos Bolyai Scholarship"]}],"id":[{"id":"10.13039\/501100003825","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003549","name":"Hungarian Scientific Research Fund","doi-asserted-by":"publisher","award":["K 120154","124950"],"award-info":[{"award-number":["K 120154","124950"]}],"id":[{"id":"10.13039\/501100003549","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003549","name":"Hungarian Scientific Research Fund","doi-asserted-by":"publisher","award":["134953"],"award-info":[{"award-number":["134953"]}],"id":[{"id":"10.13039\/501100003549","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Des. Codes Cryptogr."],"published-print":{"date-parts":[[2022,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The long-standing Erd\u0151s\u2013Faber\u2013Lov\u00e1sz conjecture states that every <jats:italic>n<\/jats:italic>-uniform linear hypergaph with <jats:italic>n<\/jats:italic> edges has a proper vertex-coloring using <jats:italic>n<\/jats:italic> colors. In this paper we propose an algebraic framework to the problem and formulate a corresponding stronger conjecture. Using the Combinatorial Nullstellensatz, we reduce the Erd\u0151s\u2013Faber\u2013Lov\u00e1sz conjecture to the existence of non-zero coefficients in certain polynomials. These coefficients are in turn related to the number of orientations with prescribed in-degree sequences of some auxiliary graphs. We prove the existence of certain orientations, which verifies a necessary condition for our algebraic approach to work.<\/jats:p>","DOI":"10.1007\/s10623-021-00859-7","type":"journal-article","created":{"date-parts":[[2021,3,25]],"date-time":"2021-03-25T22:43:10Z","timestamp":1616712190000},"page":"1991-2001","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Coloring linear hypergraphs: the Erd\u0151s\u2013Faber\u2013Lov\u00e1sz conjecture and the Combinatorial Nullstellensatz"],"prefix":"10.1007","volume":"90","author":[{"given":"Oliver","family":"Janzer","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2062-5668","authenticated-orcid":false,"given":"Zolt\u00e1n L\u00f3r\u00e1nt","family":"Nagy","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,3,25]]},"reference":[{"issue":"1\u20132","key":"859_CR1","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1017\/S0963548398003411","volume":"8","author":"N Alon","year":"1999","unstructured":"Alon N.: Combinatorial Nullstellensatz. Comb. Probab. Comput. 8(1\u20132), 7\u201329 (1999).","journal-title":"Comb. Probab. Comput."},{"issue":"2","key":"859_CR2","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/BF01204715","volume":"12","author":"N Alon","year":"1992","unstructured":"Alon N., Tarsi M.: Colorings and orientations of graphs. Combinatorica 12(2), 125\u2013134 (1992).","journal-title":"Combinatorica"},{"unstructured":"Araujo-Pardo G., V\u00e1zquez-\u00c1vila A.: A note on Erd\u00f6s-Faber-Lov\u00e1sz Conjecture and edge coloring of complete graphs. (2016) arXiv preprint arXiv:1605.03374.","key":"859_CR3"},{"issue":"1","key":"859_CR4","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/BF02579174","volume":"1","author":"P Erd\u0151s","year":"1981","unstructured":"Erd\u0151s P.: On the combinatorial problems which I would most like to see solved. Combinatorica 1(1), 25\u201342 (1981).","journal-title":"Combinatorica"},{"doi-asserted-by":"crossref","unstructured":"Erd\u0151s P.: Problems and results in combinatorial analysis and graph theory. In: Annals of Discrete Mathematics vol. 38, pp. 81\u201392. Elsevier. (1988).","key":"859_CR5","DOI":"10.1016\/S0167-5060(08)70773-8"},{"issue":"2","key":"859_CR6","first-page":"113","volume":"1","author":"V Faber","year":"2010","unstructured":"Faber V.: The Erd\u00f6s-Faber-Lov\u00e1sz conjecture-the uniform regular case. J. Comb. 1(2), 113\u2013120 (2010).","journal-title":"J. Comb."},{"issue":"1","key":"859_CR7","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1002\/rsa.20843","volume":"55","author":"V Faber","year":"2019","unstructured":"Faber V., Harris D.G.: Edge-coloring linear hypergraphs with medium-sized edges. Random Struct. Algorithms 55(1), 153\u2013159 (2019).","journal-title":"Random Struct. Algorithms"},{"key":"859_CR8","doi-asserted-by":"publisher","first-page":"545","DOI":"10.4153\/CJM-1981-046-9","volume":"33","author":"N Hindman","year":"1981","unstructured":"Hindman N.: On a conjecture of Erd\u00f6s, Faber and Lov\u00e1sz about $$n$$-colourings. Can. J. Math. 33, 545\u2013549 (1981).","journal-title":"Can. J. Math."},{"issue":"7\u20138","key":"859_CR9","doi-asserted-by":"publisher","first-page":"911","DOI":"10.1016\/j.disc.2005.11.053","volume":"307","author":"B Jackson","year":"2007","unstructured":"Jackson B., Sethuraman G., Whitehead C.: A note on the Erd\u0151s-Farber-Lov\u00e1sz conjecture. Discret. Math. 307(7\u20138), 911\u2013915 (2007).","journal-title":"Discret. Math."},{"issue":"1","key":"859_CR10","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/0097-3165(92)90096-D","volume":"59","author":"J Kahn","year":"1992","unstructured":"Kahn J.: Coloring nearly-disjoint hypergraphs with n+ o (n) colors. J. Comb. Theory Ser. A 59(1), 31\u201339 (1992).","journal-title":"J. Comb. Theory Ser. A"},{"issue":"2","key":"859_CR11","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1007\/BF01204719","volume":"12","author":"J Kahn","year":"1992","unstructured":"Kahn J., Seymour P.D.: A fractional version of the Erd\u0151s-Faber-Lov\u00e1sz conjecture. Combinatorica 12(2), 155\u2013160 (1992).","journal-title":"Combinatorica"},{"unstructured":"Kang D.Y., Kelly T., K\u00fchn D., Methuku A., Osthus D.: A proof of the Erd\u0151s-Faber-Lov\u00e1sz conjecture. (2021). arXiv:2101.04698.","key":"859_CR12"},{"key":"859_CR13","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1007\/s11856-012-0020-5","volume":"192","author":"RN Karasev","year":"2012","unstructured":"Karasev R.N., Petrov F.V.: Partitions of nonzero elements of a finite field into pairs. Israel J. Math. 192, 143\u2013156 (2012).","journal-title":"Israel J. Math."},{"key":"859_CR14","doi-asserted-by":"publisher","first-page":"252","DOI":"10.1016\/j.aim.2014.09.028","volume":"277","author":"G K\u00e1rolyi","year":"2015","unstructured":"K\u00e1rolyi G., Nagy Z.L., Petrov F.V., Volkov V.: A new approach to constant term identities and Selberg-type integrals. Adv. Math. 277, 252\u2013282 (2015).","journal-title":"Adv. Math."},{"doi-asserted-by":"crossref","unstructured":"Kaul H., Mudrock J.A.: Combinatorial Nullstellensatz and DP-coloring of Graphs. (2020). arXiv preprint arXiv:2003.01112.","key":"859_CR15","DOI":"10.1016\/j.disc.2020.112115"},{"doi-asserted-by":"crossref","unstructured":"Laso\u0144 M.: A generalization of Combinatorial Nullstellensatz. the electronic journal of combinatorics, N32-N32. (2010).","key":"859_CR16","DOI":"10.37236\/481"},{"key":"859_CR17","first-page":"497","volume":"97","author":"J Mitchem","year":"2010","unstructured":"Mitchem J., Schmidt R.L.: On the Erdos-Faber-Lovasz conjecture. Ars Comb. 97, 497\u2013505 (2010).","journal-title":"Ars Comb."},{"unstructured":"Murthy T.S.: A proof of the Total Coloring Conjecture. (2020). arXiv preprint arXiv:2003.09658.","key":"859_CR18"},{"issue":"01","key":"859_CR19","doi-asserted-by":"publisher","first-page":"1250003","DOI":"10.1142\/S1793830912500036","volume":"4","author":"V Paul","year":"2012","unstructured":"Paul V., Germina K.A.: On edge coloring of hypergraphs and Erd\u0151s-Faber-Lov\u00e1sz conjecture. Discret. Math. Algorithms Appl. 4(01), 1250003 (2012).","journal-title":"Discret. Math. Algorithms Appl."},{"key":"859_CR20","first-page":"71","volume":"85","author":"D Romero","year":"2007","unstructured":"Romero D., Sanchez-Arroyo A.: Adding evidence to the Erdos-Faber-Lovasz conjecture. Ars Comb. 85, 71\u201384 (2007).","journal-title":"Ars Comb."},{"key":"859_CR21","first-page":"285","volume-title":"Advances on the Erdos-Faber-Lovasz Conjecture","author":"D Romero","year":"2007","unstructured":"Romero D., Sanchez-Arroyo A.: Advances on the Erdos-Faber-Lovasz Conjecture, vol. 34, pp. 285\u2013298. Oxford Lecture Series in Mathematics and its Applications. Oxford University Press, Oxford (2007)."},{"issue":"3","key":"859_CR22","doi-asserted-by":"publisher","first-page":"1450039","DOI":"10.1142\/S1793830914500396","volume":"6","author":"D Romero","year":"2014","unstructured":"Romero D., Alonso-Pecina F.: The Erd\u0151s\u2013Faber\u2013Lov\u00e1sz conjecture is true for $$n\\le 12$$. Discret. Math. Algorithms Appl. 6(3), 1450039 (2014).","journal-title":"Discret. Math. Algorithms Appl."},{"issue":"5\u20136","key":"859_CR23","doi-asserted-by":"publisher","first-page":"991","DOI":"10.1016\/j.disc.2007.09.026","volume":"308","author":"A S\u00e1nchez-Arroyo","year":"2008","unstructured":"S\u00e1nchez-Arroyo A.: The Erd\u0151s-Faber-Lov\u00e1sz conjecture for dense hypergraphs. Discret. Math. 308(5\u20136), 991\u2013992 (2008).","journal-title":"Discret. Math."},{"issue":"R10","key":"859_CR24","first-page":"1","volume":"15","author":"U Schauz","year":"2008","unstructured":"Schauz U.: Algebraically solvable problems: describing polynomials as equivalent to explicit solutions. Electron. J. Comb. 15(R10), 1 (2008).","journal-title":"Electron. J. Comb."},{"issue":"1","key":"859_CR25","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/BF02579285","volume":"2","author":"PD Seymour","year":"1982","unstructured":"Seymour P.D.: Packing nearly-disjoint sets. Combinatorica 2(1), 91\u201397 (1982).","journal-title":"Combinatorica"},{"key":"859_CR26","doi-asserted-by":"publisher","first-page":"354","DOI":"10.1016\/j.jctb.2018.06.004","volume":"134","author":"X Zhu","year":"2019","unstructured":"Zhu X.: The Alon-Tarsi number of planar graphs. J. Comb. Theory Ser. B 134, 354\u2013358 (2019).","journal-title":"J. Comb. Theory Ser. B"}],"container-title":["Designs, Codes and Cryptography"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10623-021-00859-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10623-021-00859-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10623-021-00859-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,8,27]],"date-time":"2022-08-27T15:14:30Z","timestamp":1661613270000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10623-021-00859-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,3,25]]},"references-count":26,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2022,9]]}},"alternative-id":["859"],"URL":"https:\/\/doi.org\/10.1007\/s10623-021-00859-7","relation":{},"ISSN":["0925-1022","1573-7586"],"issn-type":[{"type":"print","value":"0925-1022"},{"type":"electronic","value":"1573-7586"}],"subject":[],"published":{"date-parts":[[2021,3,25]]},"assertion":[{"value":"8 July 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 January 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 February 2021","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 March 2021","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}