图与超图中的彩色匹配综述

doi:10.15960/j.cnki.issn.1007-6093.2019.03.006

摘要/Abstract

摘要： 超图H=（V，E）是一个二元组（V，E），其中超边集E中的元素是点集V的非空子集.因此图是一种特殊的超图，超图也可以看作是一般图的推广.特别地，如果超边集E中的元素均是点集V的k元子集，则称该超图为k-一致的.通常情况下，为叙述简便，我们也会将超边简称为边.图（超图）中的匹配是指图（超图）中互不相交的边的集合.对于图（超图）中的彩色匹配，有两种定义方式：一为染色图（超图）中互不相交且颜色不同的边的集合；二为顶点集均为[n]的多个染色图（超图）所构成的集族中互不相交且颜色均不同的边的集合，且每条边均来自集族中不同的图（超图）.现主要介绍了图与超图中关于彩色匹配的相关结果.

关键词: 图, 超图, 匹配, 彩色匹配

Abstract: A hypergraph H=(V, E) is a two-tuple (V, E), where the element in the hyperedge set E is a non-empty subset of the vertex set V. Therefore, the graph is a special hypergraph, and the hypergraph can also be regarded as a generalization of the general graph. In particular, if the elements in the hyperedge set E are all a k-subset of the vertex set V, then the hypergraph is said to be k-uniform. Usually, for the sake of simplicity, we will also refer to the hyperedge as the edge. A matching in a graph (hypergraph) refers to a collection of mutually disjoint edges in a graph (hypergraph). There are two ways to define a rainbow matching:one is a collection of mutually disjoint edges with different colors in an edge-colored graph(hypergraph); the other one is a collection of mutually disjoint edges with different colors, where each edge is from different edge-colored graphs(hypergraphs). This paper mainly introduces the results related to rainbow matchings in graphs and hypergraphs.

Key words: graph, hypergraph, matching, rainbow matching

中图分类号:

O157.5

李瞳, 王光辉, 周文玲. 图与超图中的彩色匹配综述[J]. 运筹学学报, 2019, 23(3): 77-90.

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 C₃'s and C₄'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.