Rainbow matchings in Dirac bipartite graphs. (English) Zbl 1426.05137
Summary: We show the existence of rainbow perfect matchings in \(\mu n\)-bounded edge colorings of Dirac bipartite graphs, for a sufficiently small \(\mu > 0\). As an application of our results, we obtain several results on the existence of rainbow \(k\)-factors in Dirac graphs and rainbow spanning subgraphs of bounded maximum degree on graphs with large minimum degree.
MSC:
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
| 05C15 | Coloring of graphs and hypergraphs |
| 05D15 | Transversal (matching) theory |
| 05C07 | Vertex degrees |
| 05C35 | Extremal problems in graph theory |
References:
| [1] | N.Alon and E.Fischer, 2‐factors in dense graphs, Discrete Math.152 (1996) no. 1, 13-23. · Zbl 0851.05068 |
| [2] | B.Bollobás and S. E.Eldridge, Packings of graphs and applications to computational complexity, J. Combin. Theory, Ser. B25 (1978) no. 2, 105-124. · Zbl 0387.05020 |
| [3] | J.Böttcher, Y.Kohayakawa, and A.Procacci, Properly coloured copies and rainbow copies of large graphs with small maximum degree, Random Structures Algorithms40 (2012) no. 4, 425-436. · Zbl 1244.05087 |
| [4] | R. A.Brualdi and H. J.Ryser, Combinatorial matrix theory. Cambridge University Press, vol. 39, 1991. · Zbl 0746.05002 |
| [5] | P. A.Catlin, Subgraphs of graphs I, Discrete Math.10 (1974) no. 2, 225-233. · Zbl 0289.05122 |
| [6] | B.Csaba, On the Bollobás‐Eldridge conjecture for bipartite graphs, Combin. Probab. Comput.16 (2007) no. 5, 661-691. · Zbl 1136.05029 |
| [7] | L.DeBiasio, D.Kühn, T.Molla, D.Osthus, and A.Taylor, Arbitrary orientations of Hamilton cycles in digraphs, SIAM J. Discrete Math.29 (2015) no. 3, 1553-1584. · Zbl 1320.05049 |
| [8] | P.Erdös and J.Spencer, Lopsided Lovász local lemma and Latin transversals, Discrete Appl. Math.30 (1991) no. 2‐3, 151-154. · Zbl 0717.05017 |
| [9] | A. B.Evans, Latin squares without orthogonal mates, Designs Codes Cryptogr.40 (2006) no. 1, 121-130. · Zbl 1180.05022 |
| [10] | J. L.Fouquet and A. P.Wojda, Mutual placement of bipartite graphs, Discrete Math.121 (1993) no. 1, 85-92. · Zbl 0791.05080 |
| [11] | P.Hatami and P. W.Shor, A lower bound for the length of a partial transversal in a Latin square, J. Combin. Theory, Ser. A115 (2008) no. 7, 1103-1113. · Zbl 1159.05303 |
| [12] | S.Janson, T.Luczak, and A.Rucinski, Random graphs. John Wiley & Sons, New York, NY, vol. 45, 2011. |
| [13] | P.Katerinis, Minimum degree of a graph and the existence of k‐factors, Proc. Indian Acad. Sci.: Math. Sci.94 (1985) no. 2, 123-127. · Zbl 0586.05030 |
| [14] | H.Kaul, A.Kostochka, and G.Yu, On a graph packing conjecture by Bollobás, Eldridge and Catlin, Combinatorica28 (2008) no. 4, 469-485. · Zbl 1212.05132 |
| [15] | M.Krivelevich, C.Lee, and B.Sudakov, Compatible Hamilton cycles in Dirac graphs, Combinatorica37 (2017) no. 4, 697-732. · Zbl 1399.05143 |
| [16] | D.Kühn, A.Lo, D.Osthus, and K.Staden, The robust component structure of dense regular graphs and applications, Proc. Lond. Math. Soc.110 (2014) no. 1, 19-56. · Zbl 1307.05130 |
| [17] | D.Kühn and D.Osthus, Proc. Int. Congr. Math.2014 (2014) no. 4, 381-406. |
| [18] | D.Kühn, D.Osthus, and A.Treglown, Hamiltonian degree sequences in digraphs, J. Combin. Theory, Ser. B100 (2010) no. 4, 367-380. · Zbl 1209.05138 |
| [19] | L.Lu and L.Székely, Using Lovász local lemma in the space of random injections, Electron. J. Combin.14 (2007) no. 1, R63. · Zbl 1183.05088 |
| [20] | M.Molloy and B.Reed, Graph colouring and the probabilistic method. Springer Science & Business Media, Berlin/Heidelberg, vol. 23, 2013. · Zbl 0926.05018 |
| [21] | J.Moon and L.Moser, On Hamiltonian bipartite graphs, Israel J. Math.1 (1963) no. 3, 163-165. · Zbl 0119.38806 |
| [22] | A.Pokrovskiy and B.Sudakov, A counterexample to Stein’s equi‐n‐square conjecture, Proc. AMS (2018). (to appear). https://doi.org/10.1090/proc/14220. · Zbl 1411.05041 · doi:10.1090/proc/14220 |
| [23] | H. J.Ryser, Neuere probleme der kombinatorik. Vortrageber Kombinatorik, Oberwolfach, 1967. |
| [24] | N.Sauer and J.Spencer, Edge disjoint placement of graphs, J. Combin. Theory, Ser. B25 (1978) no. 3, 295-302. · Zbl 0417.05037 |
| [25] | S. K.Stein, Transversals of Latin squares and their generalizations, Pacific J. Math.59 (1975) no. 2, 567-575. · Zbl 0302.05015 |
| [26] | B.Sudakov and J.Volec, Properly colored and rainbow copies of graphs with few cherries, J. Combin. Theory, Ser. B122 (2017), 391-416. · Zbl 1350.05042 |
| [27] | I. M.Wanless and B. S.Webb, The existence of Latin squares without orthogonal mates, Designs Codes Cryptogr.40 (2006) no. 1, 131-135. · Zbl 1180.05023 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
