betaFeedback

WorksMathematics

Rainbow Matchings in Kr+1K_{r+1}-free Graphs

Abstract

Let n,m,rn,m,r be positive integers with n≥2m+2n\ge 2m+2, where nn is sufficiently large relative to rr. Alon and Frankl determined the maximum number of edges in an nn-vertex graph containing neither Kr+1K_{r+1} nor a matching of size m+1m+1. In this paper, we establish a rainbow analogue of their result. More precisely, if G1,…,Gm+1G_1,\ldots,G_{m+1} are Kr+1K_{r+1}-free graphs on a common vertex set of size nn, each having more than ex⁡(n,{Kr+1,Mm+1})\operatorname{ex}(n,\{K_{r+1},M_{m+1}\}) edges, then {G1,…,Gm+1}\{G_1,\ldots,G_{m+1}\} admits a rainbow matching.

Paper details

vlnc:W_zbpcknpe
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 8

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…