Existence of rainbow matchings in strongly edge-colored graphs

详细信息    查看全文

• 作者：Guanghui Wang^a ; ^{ghwang@sdu.edu.cn" class="auth_mail" title="E-mail the corresponding author} ; Guiying Yan^b ; ^{yangy@amss.ac.cn" class="auth_mail" title="E-mail the corresponding author} ; Xiaowei Yu^a ; ^{xwyu2013@163.com" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Rainbow matchings ; Strongly edge-colored graphs ; Latin square
• 刊名：Discrete Mathematics
• 出版年：2016
• 出版时间：6 October 2016
• 年：2016
• 卷：339
• 期：10
• 页码：2457-2460
• 全文大小：343 K

文摘

The famous Ryser Conjecture states that there is a transversal of size class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16301108&_mathId=si1.gif&_user=111111111&_pii=S0012365X16301108&_rdoc=1&_issn=0012365X&md5=659193af4ada271d046125210feb4600" title="Click to view the MathML source">nclass="mathContainer hidden">class="mathCode">$n$ in a latin square of odd order class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16301108&_mathId=si1.gif&_user=111111111&_pii=S0012365X16301108&_rdoc=1&_issn=0012365X&md5=659193af4ada271d046125210feb4600" title="Click to view the MathML source">nclass="mathContainer hidden">class="mathCode">$n$, which is equivalent to finding a rainbow matching of size class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16301108&_mathId=si1.gif&_user=111111111&_pii=S0012365X16301108&_rdoc=1&_issn=0012365X&md5=659193af4ada271d046125210feb4600" title="Click to view the MathML source">nclass="mathContainer hidden">class="mathCode">$n$ in a properly edge-colored class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16301108&_mathId=si4.gif&_user=111111111&_pii=S0012365X16301108&_rdoc=1&_issn=0012365X&md5=6d17702481912a678eac23484f44b9c1" title="Click to view the MathML source">K_n,nclass="mathContainer hidden">class="mathCode">$K_{n,n}$ when class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16301108&_mathId=si1.gif&_user=111111111&_pii=S0012365X16301108&_rdoc=1&_issn=0012365X&md5=659193af4ada271d046125210feb4600" title="Click to view the MathML source">nclass="mathContainer hidden">class="mathCode">$n$ is odd. Let class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16301108&_mathId=si6.gif&_user=111111111&_pii=S0012365X16301108&_rdoc=1&_issn=0012365X&md5=4bd3259b22615666fc17a62bf16e15fd" title="Click to view the MathML source">δclass="mathContainer hidden">class="mathCode">$\delta$ denote the minimum degree of a graph. In 2011, Wang proposed a more general question to find a function class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16301108&_mathId=si7.gif&_user=111111111&_pii=S0012365X16301108&_rdoc=1&_issn=0012365X&md5=dc966b8f8f390c5c295fdc62c235a7e2" title="Click to view the MathML source">f(δ)class="mathContainer hidden">class="mathCode">$f\left(\delta \right)$ (class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16301108&_mathId=si8.gif&_user=111111111&_pii=S0012365X16301108&_rdoc=1&_issn=0012365X&md5=7d59c3f017abc0cae2db222dbd7fd42a" title="Click to view the MathML source">f(δ)≥2δ+1class="mathContainer hidden">class="mathCode">$f\left(\delta \right)\ge 2\delta +1$) such that for each properly edge-colored graph of order class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16301108&_mathId=si7.gif&_user=111111111&_pii=S0012365X16301108&_rdoc=1&_issn=0012365X&md5=dc966b8f8f390c5c295fdc62c235a7e2" title="Click to view the MathML source">f(δ)class="mathContainer hidden">class="mathCode">$f\left(\delta \right)$, there exists a rainbow matching of size class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16301108&_mathId=si6.gif&_user=111111111&_pii=S0012365X16301108&_rdoc=1&_issn=0012365X&md5=4bd3259b22615666fc17a62bf16e15fd" title="Click to view the MathML source">δclass="mathContainer hidden">class="mathCode">$\delta$. The best bound so far is class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16301108&_mathId=si11.gif&_user=111111111&_pii=S0012365X16301108&_rdoc=1&_issn=0012365X&md5=68d8401474729e3cb450c48bfa8cdf93" title="Click to view the MathML source">f(δ)≤3.5δ+2class="mathContainer hidden">class="mathCode">$f\left(\delta \right)\le 3.5\delta +2$ due to Lo. Babu et al. considered this problem in strongly edge-colored graphs in which each path of length 3 is rainbow. They proved that if class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16301108&_mathId=si12.gif&_user=111111111&_pii=S0012365X16301108&_rdoc=1&_issn=0012365X&md5=264c90162c877edb38bb42d159e5c1ad" title="Click to view the MathML source">Gclass="mathContainer hidden">class="mathCode">$G$ is a strongly edge-colored graph of order at least class="mathmlsrc">title="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16301108&_mathId=si13.gif&_user=111111111&_pii=S0012365X16301108&_rdoc=1&_issn=0012365X&md5=64df0ee3dbc1febf78d7fb7456f267e0">class="imgLazyJSB inlineImage" height="22" width="37" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0012365X16301108-si13.gif">class="mathContainer hidden">class="mathCode">$2\lfloor \frac{3\delta }{4}\rfloor$, then class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16301108&_mathId=si12.gif&_user=111111111&_pii=S0012365X16301108&_rdoc=1&_issn=0012365X&md5=264c90162c877edb38bb42d159e5c1ad" title="Click to view the MathML source">Gclass="mathContainer hidden">class="mathCode">$G$ has a rainbow matching of size class="mathmlsrc">title="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16301108&_mathId=si15.gif&_user=111111111&_pii=S0012365X16301108&_rdoc=1&_issn=0012365X&md5=705532e5fcdb6463735430f4c1c20a22">class="imgLazyJSB inlineImage" height="22" width="27" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0012365X16301108-si15.gif">class="mathContainer hidden">class="mathCode">$\lfloor \frac{3\delta }{4}\rfloor$. They proposed an interesting question: Is there a constant class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16301108&_mathId=si16.gif&_user=111111111&_pii=S0012365X16301108&_rdoc=1&_issn=0012365X&md5=3943ec39a1940c7ae2c3d8d2ffc2d60a" title="Click to view the MathML source">cclass="mathContainer hidden">class="mathCode">$c$ greater than class="mathmlsrc">title="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16301108&_mathId=si17.gif&_user=111111111&_pii=S0012365X16301108&_rdoc=1&_issn=0012365X&md5=4b50ac3f0025555498fa007f48780e7e">class="imgLazyJSB inlineImage" height="21" width="8" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0012365X16301108-si17.gif">class="mathContainer hidden">class="mathCode">$\frac{3}{4}$ such that every strongly edge-colored graph class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16301108&_mathId=si12.gif&_user=111111111&_pii=S0012365X16301108&_rdoc=1&_issn=0012365X&md5=264c90162c877edb38bb42d159e5c1ad" title="Click to view the MathML source">Gclass="mathContainer hidden">class="mathCode">$G$ has a rainbow matching of size at least class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16301108&_mathId=si19.gif&_user=111111111&_pii=S0012365X16301108&_rdoc=1&_issn=0012365X&md5=a0f7b8ea080f741d9f9b4be1742d3961" title="Click to view the MathML source">cδclass="mathContainer hidden">class="mathCode">$c\delta$ if class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16301108&_mathId=si20.gif&_user=111111111&_pii=S0012365X16301108&_rdoc=1&_issn=0012365X&md5=03b1a9a8884287c95d83f9f820d0add4" title="Click to view the MathML source">|V(G)|≥2⌊cδ⌋class="mathContainer hidden">class="mathCode">$\left|V\left(G\right)\right|\ge 2\lfloor c\delta \rfloor$? Clearly, class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16301108&_mathId=si21.gif&_user=111111111&_pii=S0012365X16301108&_rdoc=1&_issn=0012365X&md5=f201c814ffdb33e0149914381aed6d55" title="Click to view the MathML source">c≤1class="mathContainer hidden">class="mathCode">$c\le 1$. We prove that if class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16301108&_mathId=si12.gif&_user=111111111&_pii=S0012365X16301108&_rdoc=1&_issn=0012365X&md5=264c90162c877edb38bb42d159e5c1ad" title="Click to view the MathML source">Gclass="mathContainer hidden">class="mathCode">$G$ is a strongly edge-colored graph with minimum degree class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16301108&_mathId=si6.gif&_user=111111111&_pii=S0012365X16301108&_rdoc=1&_issn=0012365X&md5=4bd3259b22615666fc17a62bf16e15fd" title="Click to view the MathML source">δclass="mathContainer hidden">class="mathCode">$\delta$ and order at least class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16301108&_mathId=si24.gif&_user=111111111&_pii=S0012365X16301108&_rdoc=1&_issn=0012365X&md5=1d185241c00f1d0728cdcf276524630b" title="Click to view the MathML source">2δ+2class="mathContainer hidden">class="mathCode">$2\delta +2$, then class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16301108&_mathId=si12.gif&_user=111111111&_pii=S0012365X16301108&_rdoc=1&_issn=0012365X&md5=264c90162c877edb38bb42d159e5c1ad" title="Click to view the MathML source">Gclass="mathContainer hidden">class="mathCode">$G$ has a rainbow matching of size class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16301108&_mathId=si6.gif&_user=111111111&_pii=S0012365X16301108&_rdoc=1&_issn=0012365X&md5=4bd3259b22615666fc17a62bf16e15fd" title="Click to view the MathML source">δclass="mathContainer hidden">class="mathCode">$\delta$.