Operations Research Transactions ›› 2019, Vol. 23 ›› Issue (3): 77-90.doi: 10.15960/j.cnki.issn.1007-6093.2019.03.006
Special Issue: 第六届中国运筹学会科学技术奖获奖者专辑
Previous Articles Next Articles
LI Tong, WANG Guanghui, ZHOU Wenling*
Received:2019-06-25
Online:2019-09-15
Published:2019-09-09
CLC Number:
LI Tong, WANG Guanghui, ZHOU Wenling. A survey on rainbow matchings in graphs and hypergraphs[J]. Operations Research Transactions, 2019, 23(3): 77-90.
| [1] Erdös P, Gallai T.On the maximal paths and circuits of graphs[J].Acta Mathematica Hungarica, 1959, 10(3-4):337-357. [2] Schiermeyer I.Rainbow numbers for matchings and complete graphs[J].Discrete Mathematics, 2004, 286(1-2):157-162. [3] Fujita S, Magnant C, Ozeki K.Rainbow generalizations of Ramsey theory-a dynamic survey[J].Theory and Applications of Graphs,2014, 1:1-39. [4] Ryser H J.Neuere probleme der kombinatorik.Vorträge über Kombinatorik, Oberwolfach[M]. 1967, 69-91. [5] Garey M R, Johnson D S.Computers and Intractability:A Guide to the Theory of NP-Completeness[M]. San Francisco:W.H. Freeman & Company, 1979. [6] Stein S K.Transversals of Latin squares and their generalizations[J].Pacific Journal of Mathematics, 1975, 59(2):567-575. [7] Brualdi R A, Ryser H J.Combinatorial Matrix Theory[M]. Cambridge:Cambridge University Press, 1991. [8] Hatami P, Shor P W.A lower bound for the length of a partial transversal in a Latin square[J].Journal of Combinatorial Theory, Series A, 2008, 115(7):1103-1113. [9] Garey M R, Johnson D S.Computers and Intractability[M].New York:Freeman, 1979. [10] Kano M.Some results and problems on colored graphs[J].Lecture in Nankai University, 2006, 25:1-10. [11] Fujita S, Kaneko A, Schiermeyer I, et al.A rainbow k-matching in the complete graph with r colors[J].Electronic Journal of Combinatorics, 2009, 16(1):R51. [12] Wang G, Li H.Heterochromatic matchings in edge-colored graphs[J].Electronic Journal of Combinatorics, 2008, 115(1):R138. [13] LeSaulnier T D, Stocker C, Wenger P S, West D B.Rainbow matching in edge-colored graphs[J].Electronic Journal of Combinatorics, 2010, 17(1):R138. [14] Kostochka A, Yancey M. Large rainbow matchings in edge-coloured graphs[J].Combinatorics, Probability and Computing, 2012, 21(1-2):255-263. [15] Deza M, Frankl P.Erdös-Ko-Rado theorem-22 years later[J].SIAM Journal on Algebraic Discrete Methods, 1983, 4(4):419-431. [16] Wang G.Rainbow matchings in properly edge colored graphs[J].Electronic Journal of Combinatorics, 2013, 18(18):R162. [17] Diemunsch J, Ferrara M, Moffatt C, et al.Rainbow matchings of size δ(G) in properly edge-colored graphs[J]. arXiv:1108.2521. [18] Lo A.A note on rainbow matchings in properly edge-coloured graphs[J]. arXiv:1108.5273. [19] Diemunsch J, Ferrara M, Lo A, et al.Rainbow matchings of size δ(G) in properly edge-colored graphs[J].Electronic Journal of Combinatorics, 2011, 19(2):974-984. [20] Wang G, Zhang J, Liu G.Existence of rainbow matchings in properly edge-colored graphs[J].Frontiers of Mathematics in China, 2012, 7(3):543-550. [21] Gyárfás A, Sarkozy G N.Rainbow matchings and cycle-free partial transversals of Latin squares[J].Discrete Mathematics, 2014, 327:96-102. [22] Kostochka A, Pfender F, Yancey M.Large rainbow matchings in large graphs[J]. arXiv:1204.3193. [23] Lo A, Tan T S.A note on large rainbow matchings in edge-coloured graphs[J].Graphs and Combinatorics, 2014, 30(2):389-393. [24] Lo A.Existences of rainbow matchings and rainbow matching covers[J].Discrete Mathematics, 2015, 338(11):2119-2124. [25] Babu J, Chandran L S, Vaidyanathan K.Rainbow matchings in strongly edge-colored graphs[J].Discrete Mathematics, 2015, 338(7):1191-1196. [26] Wang G, Yan G, Yu X.Existence of rainbow matchings in strongly edge-colored graphs[J].Discrete Mathematics, 2016, 339(10):2457-2460. [27] Cheng Y, Tan T S, Wang G.A note on rainbow matchings in strongly edge-colored graphs[J].Discrete Mathematics, 2018, 341(10):2762-2767. [28] Aharoni R, Berger E.Rainbow matchings in r-partite r-graphs[J].Electronic Journal of Combinatorics, 2009, 16:R119. [29] Aharoni R, Charbit P, Howard D.On a generalization of the Ryser-Brualdi-Stein conjecture[J].Journal of Graph Theory, 2015, 78(2):143-156. [30] Kotlar D, Ziv R.Large matchings in bipartite graphs have a rainbow matching[J].Electronic Journal of Combinatorics, 2014, 38:97-101. [31] Pokrovskiy A.Rainbow matchings and connectedness of coloured graphs[J].Electronic Notes in Discrete Mathematics, 2015, 49:371-376. [32] Pokrovskiy A.An approximate version of a conjecture of Aharoni and Berger[J].Advances in Mathematics, 2018, 333:1197-1241. [33] Cano P, Perarnau G, Serra O.Rainbow perfect matchings in r-partite graph structures[J].Electronic Notes in Discrete Mathematics, 2016, 54:193-198. [34] Drisko A A.Transversals in row-latin rectangles[J].Journal of Combinatorial Theory, Series A,1998, 84:181-195. [35] Barát J, Gyárfás A, Sárközy G N.Rainbow matchings in bipartite multigraphs[J].Periodica Mathematica Hungarica, 2017, 74(1):108-111. [36] Clemens D, Ehrenmüller J.An improved bound on the sizes of matchings guaranteeing a rainbow matching[J].Mathematics, 2015, 19(11):2119-2124. [37] Aharoni R, Berger F, Chudnovsky M, et al.Large rainbow matchings in general graphs[J].European Journal of Combinatorics,2019, 79:222-227. [38] Erdös P.A problem on independent r-tuples[J].Annales Universitatis Scientiarium Budapestinensis, 1965, 8:93-95. [39] Erdös P, Ko C, Rado R.Intersection theorems for systems of finite sets[J].Quarterly Journal of Mathematics Oxford Series (2), 1961, 12:313-320. [40] Bollobás B, Daykin D E, Erdös P.Sets of independent edges of a hypergraph[J]. Quarterly Journal of Mathematics Oxford Series (2), 1976, 27:25-32. [41] Huang H, Loh P, Sudakov B.The size of a hypergraph and its matching number[J]. Combinatorics, Probability and Computing, 2012, 21:442-450. [42] Frankl P, Łuczak T, Mieczkowska K.On matchings in hypergraphs[J].Electronic Journal of Combinatorics, 2012, 19(2):596-602. [43] Frankl P.Improved bounds for Erdös matching conjecture[J].Journal of Combinatorial Theory, Series A, 2013, 120:1068-1072. [44] Erdös P, Gallai T.On the minimal number of vertices representing the edges of a graph[J].Publication of the Mathematical Institute of the Hungrian Academy of Sciences, 1961, 6:181-203. [45] Frankl P, Rödl V, Ruciński A.On the maximum number of edges in a triple system not containing a disjoint family of a given size[J].Combinatorics, Probability and Computing, 2012, 21:141-148. [46] Łuczak T, Mieczkowska K.On Erdös'extremal problem on matchings in hypergraphs[J].Journal of Combinatorial Theory, Series A, 2014, 124:178-194. [47] Frankl P.On the maximum number of edges in a hypergraph with given matching number[J].Discrete Applied Mathematics, 2017, 216:562-581. [48] Frankl P, Rödl V, Ruciński A.A short proof of Erdös'conjecture for triple systems[J].Acta Mathematica Hungarica, 2017, 151(2):495-509. [49] Frankl P.The shifting technique in extremal set theory[J].Surveys in Combinatorics, 1987, 29(2):87-110. [50] Keevash P, Mubayi D, Sudakov B, et al.Rainbow Turán problems[J].Combinatorics, Probability and Computing, 2007, 16(1):109-126. [51] Johnston D, Palmer C, Sarkar A.Rainbow Turán problems for paths and forests of stars[J].The Electronic Journal of Combinatorics, 2017, 24(1):1-34. [52] Alon N, Pokrovskiy A, Sudakov B.Random subgraphs of properly edge-coloured complete graphs and long rainbow cycles[J].Israel Journal of Mathematics, 2016, 222(1):317-331. [53] Kano M, Li X.Monochromatic and heterochromatic subgraphs in edge-colored graphs-a survey[J].Graphs and Combinatorics, 2008, 24(4):237-263. [54] Li H.Rainbow C3's and C4's in edge-colored graphs[J].Discrete Mathematics, 2013, 313(19):1893-1896. [55] Li H, Wang G.Color degree and heterochromatic cycles in edge-colored graphs[J].European Journal of Combinatorics, 2012, 33(8):1958-1964. [56] Xu C, Hu X, Wang W, Zhang S.Rainbow cliques in edge-colored graphs[J].European Journal of Combinatorics, 2016, 54:193-200. [57] Huang H, Li T, Wang G.Rainbow matchings in properly-colored hypergraphs[J].Electronic Journal of Combinatorics, 2019, 26(1):#P1.4. [58] Aharoni R, Howard D.A rainbow r-partite version of the Erdös-Ko-Rado theorem[J].Combinatorics, Probability and Computing, 2017, 26:321-337. [59] Matsumoto M, Tokushige N.The exact bound in the Erdös-Ko-Rado theorem for cross-intersect-ing families[J].Journal of Combinatorial Theory, Series A, 1989, 52:90-97. [60] Pyber L.A new generalization of the Erdös-Ko-Rado theorem[J].Journal of Combinatorial Theory, Series A, 1986, 43:85-90. [61] Akiyama J, Frankl P.On the size of graphs with complete-factors[J].Journal of Graph Theory, 1985, 9:197-201. [62] Aharoni R, Howard D.Size conditions for the existence of rainbow matching.. [63] Lu H, Yu X.On rainbow matchings for hypergraphs[J].SIAM Journal on Discrete Mathematics, 2018, 32(1):382-393. [64] Glebov R, Sudakov B, Szabó T.How many colors guarantee a rainbow matching?[J]. arXiv:1211.0793. [65] Bal D, Frieze A.Rainbow matchings and hamilton cycles in random graphs[J].Random Structures & Algorithms, 2016, 48(3):503-523. [66] Kano M, Li X.Monochromatic and heterochromatic subgraphs in edge-colored graphs-a survey[J].Graphs and Combinatorics, 2008, 24(4):237-263. |
| [1] | GAO Wei, WANG Weifan. Isolated toughness variant and the existence of fractional [a,b]-factor [J]. Operations Research Transactions, 2026, 30(1): 256-266. |
| [2] | Xue JI, Liying KANG, Yisai XUE. The extremal problem of spanning linear forests [J]. Operations Research Transactions, 2025, 29(4): 94-102. |
| [3] | Guidong YU, Hui YUAN, Xinyu XIE. The second largest signless Laplacian spectral radius of uniform supertree with diameter [J]. Operations Research Transactions, 2025, 29(4): 241-248. |
| [4] | Jiaao LI, Bo SU. Nowhere-zero 5-flows for graphs with bounded genus [J]. Operations Research Transactions, 2025, 29(3): 124-134. |
| [5] | Minghui YU. Proper polychromatic 4-coloring of subcubic bipartite plane graphs [J]. Operations Research Transactions, 2025, 29(2): 95-102. |
| [6] | Xintian LIU, Wenxing ZHU. A discrete iterative method for hypergraph bananced bi-partitioning [J]. Operations Research Transactions, 2025, 29(2): 128-140. |
| [7] | Zhiwei WU, Liying KANG. The extremal p-spectral radius of cancellative hypergraphs [J]. Operations Research Transactions, 2025, 29(2): 194-200. |
| [8] | Liangli DU, Bing WANG. Planar Turán numbers of {C5, C6} [J]. Operations Research Transactions, 2025, 29(2): 221-229. |
| [9] | Miaohui HE, Xuxiang DUAN, Zhiyou WU. A new algorithm for improving the completion performance of knowledge graph of long-tail data [J]. Operations Research Transactions, 2025, 29(1): 41-54. |
| [10] | Yao WEN, Junhua HU. Efficiency evaluation for the serial system in the absence of a given leader-follower order in the non-cooperative case [J]. Operations Research Transactions, 2025, 29(1): 77-97. |
| [11] | Yu YANG, Zhongxun ZHU, Junpeng ZHOU. The extremal k-uniform hypergraphs with given number of pendent vertices on signless Laplacian spectral radius [J]. Operations Research Transactions, 2025, 29(1): 185-197. |
| [12] | Baoxin LI, Shengjin JI. Total forcing and zero forcing of unicyclic graphs [J]. Operations Research Transactions, 2025, 29(1): 198-206. |
| [13] | Chaoping WANG, Mengmeng LIU. Steiner k-hyper Wiener index of graph products [J]. Operations Research Transactions, 2025, 29(1): 216-224. |
| [14] | Linming QI, Weiliang ZHAO, Lianying MIAO. The lower limit of the independence number in edge chromatic critical graphs [J]. Operations Research Transactions, 2025, 29(1): 225-231. |
| [15] | Xianya GENG, Hui CHAI. Gallai's conjecture for complete bipartite graphs [J]. Operations Research Transactions, 2025, 29(1): 232-238. |
| Viewed | ||||||
|
Full text |
|
|||||
|
Abstract |
|
|||||