Operations Research Transactions ›› 2019, Vol. 23 ›› Issue (3): 77-90.doi: 10.15960/j.cnki.issn.1007-6093.2019.03.006
Previous Articles Next Articles
LI Tong, WANG Guanghui, ZHOU Wenling*
Received:
2019-06-25
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.. http://math.colgate.edu/dmhoward/rsc.pdf. [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] | LIU Zhiping. Some advances in gene regulatory network inference [J]. Operations Research Transactions, 2021, 25(3): 173-182. |
[2] | LAN Yongxin, SHI Yongtang, SONG Zixia. Planar Turán number and planar anti-Ramsey number of graphs [J]. Operations Research Transactions, 2021, 25(3): 200-216. |
[3] | LIU Yao. On (1, 0)-relaxed strong edge-coloring of graphs [J]. Operations Research Transactions, 2021, 25(2): 115-126. |
[4] | DONG Yanxia, XUE Tao, ZHANG Guang. k-tuple domination in generalized de Bruijn digraphs [J]. Operations Research Transactions, 2021, 25(2): 127-134. |
[5] | BAO Xiaoguang, LU Chao, HUANG Dongmei, YU Wei. Approximation algorithm for min-max cycle cover problem on a mixed graph [J]. Operations Research Transactions, 2021, 25(1): 107-113. |
[6] | ZHAO Jing, SHAN Erfang, ZHAO Jiagui. Sufficient conditions for hypergraphs to be maximally edge-connected and super-edge-connected [J]. Operations Research Transactions, 2021, 25(1): 123-131. |
[7] | CHEN Min, YANG Jianmin, ZHANG Hao, WANG Yiting. Weakly entire coloring of outerplanar graphs [J]. Operations Research Transactions, 2021, 25(1): 132-136. |
[8] | LIN Xiaoxia. A note on quasi k-connected graphs [J]. Operations Research Transactions, 2021, 25(1): 137-140. |
[9] | YU Guidong, RUAN Zheng, SHU Axiu, YU Tao. The second maximum (Laplacian) separator of unicyclic graphs [J]. Operations Research Transactions, 2020, 24(4): 128-134. |
[10] | TONG Linken, SHAN Erfang. The restricted edge-connectivity and λ'-optimality of hypergraphs [J]. Operations Research Transactions, 2020, 24(4): 145-152. |
[11] | LIN Hao, LIN Lan. Optimality characterization of the minimum stretch spanning tree problem for interval graphs [J]. Operations Research Transactions, 2020, 24(4): 153-158. |
[12] | CHEN Hongling, WANG Huijuan, SUN Fengyan, XUE Juan, GAO Hongwei. Linear arboricity of planar graphs with maximum degree at least seven [J]. Operations Research Transactions, 2020, 24(3): 154-160. |
[13] | CHEN Tao. Upper bounds on minimum balanced bipartition of Hamilton plane graphs [J]. Operations Research Transactions, 2020, 24(3): 161-166. |
[14] | TIAN Shuangliang, YANG Huan, SUOLANG Wangqing, YANG Qing. Neighbor sum distinguishing edge coloring of the lexicographic product of paths [J]. Operations Research Transactions, 2020, 24(1): 140-146. |
[15] | LIN Yang, WANG Yingming. Two-sided game matching with uncertain preference ordinal [J]. Operations Research Transactions, 2020, 24(1): 155-162. |
Viewed | ||||||
Full text |
|
|||||
Abstract |
|
|||||