Name
Abstract | ||
|---|---|---|
The famous Ryser Conjecture states that there is a transversal of size n in a latin square of odd order n , which is equivalent to finding a rainbow matching of size n in a properly edge-colored K n , n when n is odd. Let ź denote the minimum degree of a graph. In 2011, Wang proposed a more general question to find a function f ( ź ) ( f ( ź ) ź 2 ź + 1 ) such that for each properly edge-colored graph of order f ( ź ) , there exists a rainbow matching of size ź . The best bound so far is f ( ź ) ź 3.5 ź + 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 G is a strongly edge-colored graph of order at least 2 ź 3 ź 4 ź , then G has a rainbow matching of size ź 3 ź 4 ź . They proposed an interesting question: Is there a constant c greater than 3 4 such that every strongly edge-colored graph G has a rainbow matching of size at least c ź if | V ( G ) | ź 2 ź c ź ź ? Clearly, c ź 1 . We prove that if G is a strongly edge-colored graph with minimum degree ź and order at least 2 ź + 2 , then G has a rainbow matching of size ź . |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1016/j.disc.2016.04.016 | Discrete Mathematics |
Keywords | Field | DocType |
Rainbow matchings,Strongly edge-colored graphs,Latin square | Discrete mathematics,Graph,Colored,Combinatorics,Transversal (geometry),Rainbow,Conjecture,Mathematics | Journal |
Volume | Issue | ISSN |
339 | 10 | 0012-365X |
Citations | PageRank | References |
3 | 0.45 | 16 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Guanghui Wang | 1 | 199 | 23.23 |
| Guiying Yan | 2 | 196 | 22.92 |
| Xiaowei Yu | 3 | 3 | 0.45 |