Bipartite rainbow numbers of matchings |
| |
Authors: | Xueliang Li Jianhua Tu |
| |
Affiliation: | a Center for Combinatorics and LPMC-TJKLC, Nankai University, Tianjin 300071, PR China b Department of Mathematics, Zhejiang Normal University, Jinhua, Zhejiang 321004, PR China |
| |
Abstract: | Given two graphs G and H, let f(G,H) denote the maximum number c for which there is a way to color the edges of G with c colors such that every subgraph H of G has at least two edges of the same color. Equivalently, any edge-coloring of G with at least rb(G,H)=f(G,H)+1 colors contains a rainbow copy of H, where a rainbow subgraph of an edge-colored graph is such that no two edges of it have the same color. The number rb(G,H) is called the rainbow number ofHwith respect toG, and simply called the bipartite rainbow number ofH if G is the complete bipartite graph Km,n. Erd?s, Simonovits and Sós showed that rb(Kn,K3)=n. In 2004, Schiermeyer determined the rainbow numbers rb(Kn,Kk) for all n≥k≥4, and the rainbow numbers rb(Kn,kK2) for all k≥2 and n≥3k+3. In this paper we will determine the rainbow numbers rb(Km,n,kK2) for all k≥1. |
| |
Keywords: | Edge-coloring Rainbow subgraph Rainbow number |
本文献已被 ScienceDirect 等数据库收录! |
|