{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:45:24Z","timestamp":1787323524589,"version":"build-2736575974"},"reference-count":32,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"DOI":"10.13039\/501100004895","name":"European Social Fund","doi-asserted-by":"publisher","award":["EFOP-3.6.3-VEKOP-16-2017-00002"],"award-info":[{"award-number":["EFOP-3.6.3-VEKOP-16-2017-00002"]}],"id":[{"id":"10.13039\/501100004895","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003825","name":"Magyar Tudom\u00e1nyos Akad\u00e9mia","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100003825","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100012550","name":"Nemzeti Kutat\u00e1si, Fejleszt\u00e9si \u00e9s Innovaci\u00f3s Alap","doi-asserted-by":"publisher","award":["FK 18"],"award-info":[{"award-number":["FK 18"]}],"id":[{"id":"10.13039\/501100012550","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100012550","name":"Nemzeti Kutat\u00e1si, Fejleszt\u00e9si \u00e9s Innovaci\u00f3s Alap","doi-asserted-by":"publisher","award":["UNKP-20-5"],"award-info":[{"award-number":["UNKP-20-5"]}],"id":[{"id":"10.13039\/501100012550","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100012550","name":"Nemzeti Kutat\u00e1si, Fejleszt\u00e9si \u00e9s Innovaci\u00f3s Alap","doi-asserted-by":"publisher","award":["TKP2020-NKA-06"],"award-info":[{"award-number":["TKP2020-NKA-06"]}],"id":[{"id":"10.13039\/501100012550","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004206","name":"Osaka University","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100004206","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:p>In the list coloring problem for two matroids, we are given matroids $M_1=(S,{\\mathcal{I}}_1)$ and $M_2=(S,{\\mathcal{I}}_2)$ on the same ground set $S$, and the goal is to determine the smallest number $k$ such that, given arbitrary lists $L_s$ of $k$ colors for $s\\in S$, it is possible to choose a color from each list so that every monochromatic set is independent in both $M_1$ and $M_2$. When both $M_1$ and $M_2$ are partition matroids, Galvin's celebrated list coloring theorem for bipartite graphs gives the answer. However, not much is known about the general case. One of the main open questions is to decide if there exists a constant $c$ such that if the coloring number is $k$ (i.e., the ground set can be partitioned into $k$ common independent sets), then the list coloring number is at most $c\\cdot k$. In the present paper, we consider matroid classes that appear naturally in combinatorial and graph optimization problems, specifically graphic matroids, paving matroids and gammoids. We show that if both matroids are from these fundamental classes, then the list coloring number is at most twice the coloring number. The proof is based on a new approach that reduces a matroid to a partition matroid without increasing its coloring number too much and might be of independent combinatorial interest. In particular, we show that if $M=(S,{\\mathcal{I}})$ is a matroid in which $S$ can be partitioned into $k$ independent sets, then there exists a partition matroid $N=(S,{\\mathcal{J}})$ with ${\\mathcal{J}}\\subseteq{\\mathcal{I}}$ in which $S$ can be partitioned into (A) $k$ independent sets if $M$ is a transversal matroid, (B) $2k-1$ independent sets if $M$ is a graphic matroid, (C) $\\lceil kr\/(r-1)\\rceil$ independent sets if $M$ is a paving matroid of rank $r$, and (D) $2k-2$ independent sets if $M$ is a gammoid. It should be emphasized that in cases (A), (B), and (D) the rank of $N$ is the same as that of $M$. We further extend our results to a much broader family by showing that taking direct sum, homomorphic image, or truncation of matroids from these classes results in a matroid admitting a reduction to a partition matroid with coloring number at most twice the original one.<\/jats:p>","DOI":"10.1137\/20m1385615","type":"journal-article","created":{"date-parts":[[2021,9,20]],"date-time":"2021-09-20T12:00:46Z","timestamp":1632139246000},"page":"2192-2209","source":"Crossref","is-referenced-by-count":6,"title":["List Coloring of Two Matroids through Reduction to Partition Matroids"],"prefix":"10.1137","volume":"35","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0457-4573","authenticated-orcid":true,"given":"Krist\u00f3f","family":"B\u00e9rczi","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tam\u00e1s","family":"Schwarcz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yutaro","family":"Yamaguchi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2021,9,20]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-06-03833-5"},{"key":"atypb2","unstructured":"A. Bialostocki, P. Dierker, and W. Voxman,\n                      Either a Graph or Its Complement is Connected: A Continuing Saga\n                      , manuscript, 2001."},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1973-0419270-0"},{"key":"atypb4","unstructured":"K. B\u00e9rczi and T. Schwarcz,\n                      Rainbow and Monochromatic Circuits and Cuts in Binary Matroids\n                      , preprint, arXiv:2012.05037, 2020,https:\/\/arxiv.org\/abs\/2012.05037."},{"key":"atypb5","doi-asserted-by":"crossref","unstructured":"H. H. Crapo and G.C. Rota,\n                      On the Foundations of Combinatorial Theory: Combinatorial Geometries\n                      , MIT Press, Cambridge, MA, 1970.","DOI":"10.1002\/sapm1970492109"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s2-14.1.55"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.6028\/jres.069B.016"},{"key":"atypb8","unstructured":"A. Frank,\n                      Connections in Combinatorial Optimization\n                      , Oxford Lecture Series in Mathematics and Its Applications 38, Oxford University Press, Oxford, uk, 2011."},{"key":"atypb9","unstructured":"G. Frobenius,\n                      \u00dcber zerlegbare Determinanten\n                      , Reimer, Berlin, 1917."},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1995.1011"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-10.37.26"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1959-013-8"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2020.11.003"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(73)90031-2"},{"key":"atypb15","unstructured":"T. R. Jensen and B. Toft,\n                      Graph Coloring Problems\n                      , vol. 39, John Wiley & Sons, Hoboken, NJ, 2011."},{"key":"atypb16","unstructured":"T. Kir\u00e1ly,\n                      EGRES Open: Research forum of the Egerv\u00e1ry Research Group\n                      , 2013,http:\/\/lemon.cs.elte.hu\/egres\/open\/List_colouring_of_two_matroids(accessed 2019-11-10)."},{"key":"atypb17","first-page":"36","author":"Kir\u00e1ly T.","year":"2013","journal-title":"Proceedings of the Midsummer Combinatorial Workshop"},{"key":"atypb18","unstructured":"T. Kir\u00e1ly and J. Pap,\n                      On the List Colouring of Two Matroids\n                      , tech. report QP-2010-01, Egerv\u00e1ry Research Group, Budapest, 2010,http:\/\/www.cs.elte.hu\/egres."},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1007\/BF01456961"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2015.04.004"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1007\/BF01894789"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1974-13386-0"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1975-0371693-2"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2011.01.016"},{"key":"atypb25","first-page":"12","volume":"1","author":"C. S.","year":"1964","journal-title":"J. Lond. Math. Soc."},{"key":"atypb26","doi-asserted-by":"crossref","unstructured":"H. Nishimura and S. Kuroda,\n                      A Lost Mathematician, Takeo Nakasawa: The Forgotten Father of Matroid Theory\n                      , Springer Science & Business Media, New York, 2009.","DOI":"10.1007\/978-3-7643-8573-6"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.37236\/4899"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1997.1784"},{"key":"atypb29","first-page":"25","volume":"3","author":"Vizing V. G.","year":"1964","journal-title":"Diskret. Analiz"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1007\/BF01885700"},{"key":"atypb31","unstructured":"D. J. Welsh,\n                      Matroid Theory\n                      , Courier Corporation, North Chelmsford, MA, 2010."},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.2307\/2371182"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/20M1385615","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:07:27Z","timestamp":1787321247000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/20M1385615"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1]]},"references-count":32,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["10.1137\/20M1385615"],"URL":"https:\/\/doi.org\/10.1137\/20m1385615","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1]]}}}