Loading...
Please wait, while we are loading the content...
Similar Documents
Large Rainbow Matchings in Edge-Coloured Graphs
| Content Provider | Scilit |
|---|---|
| Author | Kostochka, Alexandr Yancey, Matthew |
| Copyright Year | 2012 |
| Description | Arainbow subgraphof an edge-coloured graph is a subgraph whose edges have distinct colours. Thecolour degreeof a vertexvis the number of different colours on edges incident withv. Wang and Li conjectured that fork≥ 4, every edge-coloured graph with minimum colour degreekcontains a rainbow matching of size at least ⌈k/2⌉. A properly $edge-colouredK_{4}$has no such matching, which motivates the restrictionk≥ 4, but Li and Xu proved the conjecture for all other properly coloured complete graphs. LeSaulnier, Stocker, Wenger and West showed that a rainbow matching of size ⌊k/2⌋ is guaranteed to exist, and they proved several sufficient conditions for a matching of size ⌈k/2⌉. We prove the conjecture in full. |
| Related Links | http://www.math.uiuc.edu/~kostochk/docs/2012/cpc12y.pdf https://www.cambridge.org/core/services/aop-cambridge-core/content/view/9864FA36742C55395A040C396899BFAC/S0963548311000605a.pdf/div-class-title-large-rainbow-matchings-in-edge-coloured-graphs-div.pdf |
| Ending Page | 263 |
| Page Count | 9 |
| Starting Page | 255 |
| ISSN | 09635483 |
| e-ISSN | 14692163 |
| DOI | 10.1017/s0963548311000605 |
| Journal | Combinatorics, Probability and Computing |
| Issue Number | 1-2 |
| Volume Number | 21 |
| Language | English |
| Publisher | Cambridge University Press (CUP) |
| Publisher Date | 2012-03-01 |
| Access Restriction | Open |
| Subject Keyword | Combinatorics, Probability and Computing Mathematical Physics Large Rainbow Matchings Complete Graph Distinct Colour coloured K4 Restriction K Edges Incident Colour Degree Rainbow Subgraph Different Colour Minimum Colour Degree K coloured Graph |
| Content Type | Text |
| Resource Type | Article |
| Subject | Applied Mathematics Statistics and Probability Theoretical Computer Science Computational Theory and Mathematics |
