Abstract | ||
---|---|---|
An edge-colored graph H is called rainbow if e(H)=c(H), where e(H) and c(H) are the number of edges of H and colors used in H, respectively. For two graphs G and H, the rainbow number rb(G,H) is the minimum number of colors k such that for every edge-coloring of G using k colors, G contains a rainbow H. In this paper we prove that for an edge-colored graph G on n vertices with n≥k≥4, if e(G)+c(G)≥(n2)+tn,k−2+2, then G contains a rainbow clique Kk, where tn,k−2 is the Turán number. This implies the known result rb(Kn,Kk)=tn,k−2+2, and moreover, rb(G,Kk)≤e(G¯)+rb(Kn,Kk) for n≥k≥4. |
Year | DOI | Venue |
---|---|---|
2016 | 10.1016/j.ejc.2015.12.013 | European Journal of Combinatorics |
Field | DocType | Volume |
Discrete mathematics,Graph,Colored,Turán number,Combinatorics,Vertex (geometry),Clique,Rainbow,Mathematics | Journal | 54 |
Issue | ISSN | Citations |
C | 0195-6698 | 5 |
PageRank | References | Authors |
0.47 | 2 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Chuandong Xu | 1 | 13 | 5.63 |
Xiaoxue Hu | 2 | 7 | 1.20 |
Weifan Wang | 3 | 868 | 89.92 |
Shenggui Zhang | 4 | 263 | 47.21 |