The rainbow number of matchings in regular bipartite graphs

Abstract: Given a graph

G

and a subgraph

H

of

G

, let

r b (G, H)

be the minimum number

r

for which any edge-coloring of

G

with

r

colors has a rainbow subgraph

H

. The number

r b (G, H)

is called the rainbow number of

H

with respect to

G

. Denote

m K_{2}

a matching of size

m

and

B_{n, k}

a

k

-regular bipartite graph with bipartition

(X, Y)

such that

| X | = | Y | = n

and

k l e q n

. In this paper we give an upper and lower bound for

r b (B_{n, k}, m K_{2})

, and show that for given

k

and

m

, if

n

is large enough,

r b (B_{n, k}, m K_{2})

can reach the lower bound. We also determine the rainbow number of matchings in paths and cycles.

Recommendations

Cites Work

Cited In (23)

This page was built for publication: The rainbow number of matchings in regular bipartite graphs