{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,27]],"date-time":"2025-10-27T21:06:28Z","timestamp":1761599188134,"version":"build-2065373602"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2025,9,25]],"date-time":"2025-09-25T00:00:00Z","timestamp":1758758400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,9,25]],"date-time":"2025-09-25T00:00:00Z","timestamp":1758758400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Umea University"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2025,10]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    It is known that in matroids the difference between the chromatic number and the fractional chromatic number is smaller than 1, and that the list chromatic number is equal to the chromatic number. We investigate the gap within these pairs of parameters for hypergraphs that are the intersection of a given number\n                    <jats:italic>k<\/jats:italic>\n                    of matroids. We prove that in such hypergraphs the list chromatic number is at most\n                    <jats:italic>k<\/jats:italic>\n                    times the chromatic number and at most\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$2k-1$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mn>2<\/mml:mn>\n                            <mml:mi>k<\/mml:mi>\n                            <mml:mo>-<\/mml:mo>\n                            <mml:mn>1<\/mml:mn>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    times the maximum chromatic number among the\u00a0\n                    <jats:italic>k<\/jats:italic>\n                    matroids. We study the relationship between three polytopes associated with\n                    <jats:italic>k<\/jats:italic>\n                    -sets of matroids, and connect them to bounds on the fractional chromatic number of the intersection of the members of the\n                    <jats:italic>k<\/jats:italic>\n                    -set. This also connects to bounds on the matroidal matching and covering number of the intersection of the members of the\n                    <jats:italic>k<\/jats:italic>\n                    -set. The tools used are in part topological.\n                  <\/jats:p>","DOI":"10.1007\/s00493-025-00178-8","type":"journal-article","created":{"date-parts":[[2025,9,25]],"date-time":"2025-09-25T10:59:55Z","timestamp":1758797995000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Coloring, list coloring, and fractional coloring in intersections of matroids"],"prefix":"10.1007","volume":"45","author":[{"given":"Ron","family":"Aharoni","sequence":"first","affiliation":[]},{"given":"Eli","family":"Berger","sequence":"additional","affiliation":[]},{"given":"He","family":"Guo","sequence":"additional","affiliation":[]},{"given":"Dani","family":"Kotlar","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,9,25]]},"reference":[{"key":"178_CR1","first-page":"223","volume":"28","author":"R Aharoni","year":"2002","unstructured":"Aharoni, R.: Ryser\u2019s conjecture for tripartite hypergraphs. Combinatorica 28, 223\u2013229 (2002)","journal-title":"Combinatorica"},{"key":"178_CR2","doi-asserted-by":"publisher","first-page":"4895","DOI":"10.1090\/S0002-9947-06-03833-5","volume":"358","author":"R Aharoni","year":"2006","unstructured":"Aharoni, R., Berger, E.: The intersection of a matroid and a simplicial complex. Trans. Am. Math. Soc. 358, 4895\u20134917 (2006)","journal-title":"Trans. Am. Math. Soc."},{"key":"178_CR3","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1007\/s00039-005-0516-9","volume":"15","author":"R Aharoni","year":"2005","unstructured":"Aharoni, R., Berger, E., Meshulam, R.: Eigenvalues and homology of flag complexes and vector representations of graphs. Geom. Funct. Anal. 15, 555\u2013566 (2005)","journal-title":"Geom. Funct. Anal."},{"key":"178_CR4","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1007\/s00454-002-2792-6","volume":"28","author":"R Aharoni","year":"2002","unstructured":"Aharoni, R., Chudnovsky, M., Kotlov, A.: Triangulated spheres and colored cliques. Discrete Comput. Geom. 28, 223\u2013229 (2002)","journal-title":"Discrete Comput. Geom."},{"key":"178_CR5","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1002\/1097-0118(200010)35:2<83::AID-JGT2>3.0.CO;2-V","volume":"35","author":"R Aharoni","year":"2000","unstructured":"Aharoni, R., Haxell, P.: Hall\u2019s theorem for hypergraphs. J. Graph Theory 35, 83\u201388 (2000)","journal-title":"J. Graph Theory"},{"key":"178_CR6","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/S0012-365X(96)00159-8","volume":"165\u2013166","author":"N Alon","year":"1997","unstructured":"Alon, N., Tuza, Z., Voigt, M.: Choosability and fractional chromatic numbers. Discrete Math. 165\u2013166, 31\u201338 (1997)","journal-title":"Discrete Math."},{"key":"178_CR7","doi-asserted-by":"publisher","first-page":"2192","DOI":"10.1137\/20M1385615","volume":"35","author":"K B\u00e9rczi","year":"2021","unstructured":"B\u00e9rczi, K., Schwarcz, T., Yamaguchi, Y.: List coloring of two matroids through reduction to partition matroids. SIAM J. Discrete Math. 35, 2192\u20132209 (2021)","journal-title":"SIAM J. Discrete Math."},{"key":"178_CR8","doi-asserted-by":"crossref","unstructured":"Berger, E., Guo, H.: Coloring the intersection of two matroids. Proc. Amer. Math. Soc. 153, 4145\u20134154 (2025)","DOI":"10.1090\/proc\/17274"},{"key":"178_CR9","doi-asserted-by":"publisher","first-page":"67","DOI":"10.6028\/jres.069B.004","volume":"69","author":"J Edmonds","year":"1965","unstructured":"Edmonds, J.: Minimum partition of a matroid into independent subsets. J. Res. Nat. Bur. Standards Sect. B 69, 67\u201372 (1965)","journal-title":"J. Res. Nat. Bur. Standards Sect. B"},{"key":"178_CR10","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/S0167-5060(08)70817-3","volume":"4","author":"J Edmonds","year":"1979","unstructured":"Edmonds, J.: Matroid intersection. Ann. Discrete Math. 4, 39\u201349 (1979)","journal-title":"Ann. Discrete Math."},{"key":"178_CR11","doi-asserted-by":"crossref","unstructured":"Edmonds, J.: Submodular Functions, Matroids, and Certain Polyhedra. Combinatorial Optimization \u2013 Eureka, You Shrink! Lecture Notes in Computer Science, Springer, Berlin, Heidelberg. 2570, 11\u201326 (2003)","DOI":"10.1007\/3-540-36478-1_2"},{"key":"178_CR12","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1007\/s001860300301","volume":"58","author":"SP Fekete","year":"2003","unstructured":"Fekete, S.P., Firla, R.T., Spille, B.: Characterizing matchings as the intersection of matroids. Math. Methods Oper. Res. 58, 319\u2013329 (2003)","journal-title":"Math. Methods Oper. Res."},{"key":"178_CR13","doi-asserted-by":"publisher","first-page":"328","DOI":"10.1016\/0196-6774(81)90032-8","volume":"2","author":"A Frank","year":"1981","unstructured":"Frank, A.: A weighted matroid intersection algorithm. J. Algorithms 2, 328\u2013336 (1981)","journal-title":"J. Algorithms"},{"key":"178_CR14","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1007\/BF02579271","volume":"1","author":"Z F\u00fcredi","year":"1981","unstructured":"F\u00fcredi, Z.: Maximum degree and fractional matchings in uniform hypergraphs. Combinatorica 1, 155\u2013162 (1981)","journal-title":"Combinatorica"},{"key":"178_CR15","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1007\/BF01303202","volume":"13","author":"Z F\u00fcredi","year":"1993","unstructured":"F\u00fcredi, Z., Kahn, J., Seymour, P.: On the fractional matching polytope of a hypergraph. Combinatorica 13, 167\u2013180 (1993)","journal-title":"Combinatorica"},{"key":"178_CR16","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1006\/jctb.1995.1011","volume":"63","author":"F Galvin","year":"1995","unstructured":"Galvin, F.: The list chromatic index of a bipartite multigraph. J. Combin. Theory Ser. B 63, 153\u2013158 (1995)","journal-title":"J. Combin. Theory Ser. B"},{"key":"178_CR17","unstructured":"Guo, H.: The list chromatic number of the intersection of two generalized partition matroids. Preprint (2024). arXiv:2407.08796"},{"key":"178_CR18","volume-title":"Algebraic topology","author":"A Hatcher","year":"2001","unstructured":"Hatcher, A.: Algebraic topology. Cambridge University Press, Cambridge (2001)"},{"key":"178_CR19","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/j.orl.2020.11.003","volume":"49","author":"S Im","year":"2021","unstructured":"Im, S., Moseley, B., Pruhs, K.: The matroid intersection cover problem. Oper. Res. Lett. 49, 17\u201322 (2021)","journal-title":"Oper. Res. Lett."},{"key":"178_CR20","unstructured":"Imolay, A.: Intersection of matroids. Master thesis, E\u00f6tv\u00f6s Lor\u00e1nd University (2023)"},{"key":"178_CR21","doi-asserted-by":"publisher","first-page":"1910","DOI":"10.1016\/j.dam.2007.05.004","volume":"155","author":"K Kashiwabara","year":"2007","unstructured":"Kashiwabara, K., Okamoto, Y., Uno, T.: Matroid representation of clique complexes. Discrete Appl. Math. 155, 1910\u20131929 (2007)","journal-title":"Discrete Appl. Math."},{"key":"178_CR22","unstructured":"Kfir, O.: Systems of representatives and their applications. Master thesis, Technion (2005)"},{"key":"178_CR23","unstructured":"Kir\u00e1ly, T.: Egres open: Research forum of the egerv\u00e1ry research group. (2013)"},{"key":"178_CR24","unstructured":"Kir\u00e1ly, T.: Open questions on matroids and list colouring. In: Midsummer Combinatorial Workshop, 36\u201338 (2013)"},{"key":"178_CR25","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1016\/S0167-5060(08)70322-4","volume":"2","author":"B Korte","year":"1978","unstructured":"Korte, B., Hausmann, D.: An analysis of the greedy heuristic for independence systems. Ann. Discrete Math. 2, 65\u201374 (1978)","journal-title":"Ann. Discrete Math."},{"key":"178_CR26","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1007\/s10107-020-01524-y","volume":"183","author":"A Linhares","year":"2020","unstructured":"Linhares, A., Olver, N., Swamy, C., Zenklusen, R.: Approximate multi-matroid intersection via iterative refinement. Math. Program. 183, 397\u2013418 (2020)","journal-title":"Math. Program."},{"key":"178_CR27","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1016\/S0097-3165(03)00045-1","volume":"102","author":"R Meshulam","year":"2003","unstructured":"Meshulam, R.: Domination numbers and homology. J. Combin. Theory Ser. A 102, 321\u2013330 (2003)","journal-title":"J. Combin. Theory Ser. A"},{"key":"178_CR28","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1112\/jlms\/s1-39.1.12","volume":"s1\u201339","author":"CSA Nash-Williams","year":"1964","unstructured":"Nash-Williams, C.S.A.: Decomposition of finite graphs into forests. J. London Math. Soc. s1\u201339, 12\u201312 (1964)","journal-title":"J. London Math. Soc."},{"key":"178_CR29","volume-title":"Matroid theory","author":"JG Oxley","year":"2006","unstructured":"Oxley, J.G.: Matroid theory. Oxford University Press, USA (2006)"},{"key":"178_CR30","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1093\/qmath\/os-13.1.83","volume":"os\u201313","author":"R Rado","year":"1942","unstructured":"Rado, R.: A theorem on independence relations. Q. J. Math. os\u201313, 83\u201389 (1942)","journal-title":"Q. J. Math."},{"key":"178_CR31","volume-title":"Combinatorial optimization: polyhedra and efficiency","author":"A Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial optimization: polyhedra and efficiency, vol. 24. Springer, Berlin, Germany (2003)"},{"key":"178_CR32","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1006\/jctb.1997.1784","volume":"72","author":"P Seymour","year":"1998","unstructured":"Seymour, P.: A note on list arboricity. J. Combin. Theory Ser. B 72, 150\u2013151 (1998)","journal-title":"J. Combin. Theory Ser. B"},{"key":"178_CR33","volume-title":"Matroid theory","author":"DJ Welsh","year":"2010","unstructured":"Welsh, D.J.: Matroid theory. Courier Corporation, USA (2010)"},{"key":"178_CR34","doi-asserted-by":"publisher","first-page":"509","DOI":"10.2307\/2371182","volume":"57","author":"H Whitney","year":"1935","unstructured":"Whitney, H.: On the abstract properties of linear dependence. Amer. J. Math. 57, 509\u2013533 (1935)","journal-title":"Amer. J. Math."}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-025-00178-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00493-025-00178-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-025-00178-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,27]],"date-time":"2025-10-27T21:02:23Z","timestamp":1761598943000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00493-025-00178-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,9,25]]},"references-count":34,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2025,10]]}},"alternative-id":["178"],"URL":"https:\/\/doi.org\/10.1007\/s00493-025-00178-8","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"type":"print","value":"0209-9683"},{"type":"electronic","value":"1439-6912"}],"subject":[],"published":{"date-parts":[[2025,9,25]]},"assertion":[{"value":"1 August 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 August 2025","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 August 2025","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 September 2025","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"46"}}