Rainbow paths and large rainbow matchings

Abstract: A conjecture of the first two authors is that

n

matchings of size

n

in any graph have a rainbow matching of size

n - 1

. We prove a lower bound of

f r a c 23 n - 1

, improving on the trivial

f r a c 12 n

, and an analogous result for hypergraphs. For

C_{3}, C_{5}

-free graphs and for disjoint matchings we obtain a lower bound of

f r a c 3 n 4 - O (1)

. We also discuss a conjecture on rainbow alternating paths, that if true would yield a lower bound of

n - s q r t 2 n

. We prove the non-alternating (ordinary paths) version of this conjecture.

Full work available at URL: https://arxiv.org/abs/2012.14992

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

Cites Work

Cited In (3)

This page was built for publication: Rainbow paths and large rainbow matchings