Abstract | ||
---|---|---|
Let α(k, p, h) be the maximum number of vertices a complete edge-colored graph may have with no color appearing more than k times at any vertex and not containing a complete subgraph on p vertices with no color appearing more than h times at any vertex. We prove that α(k, p, h) ≤ h + 1 + (k − 1){(p − h − 1) × (hp + 1)}1h and obtain a stronger upper bound for α(k, 3, 1). Further, we prove that a complete edge-colored graph with n vertices contains a complete subgraph on p vertices in which no two edges have the same color if (n3)>(p3)Σi=1t(ei2) where ei is the number of edges of color i, 1 ≤ i ≤ t. |
Year | DOI | Venue |
---|---|---|
1978 | 10.1016/0095-8956(78)90045-X | Journal of Combinatorial Theory, Series B |
Field | DocType | Volume |
Graph,Discrete mathematics,Combinatorics,Vertex (geometry),Bound graph,Upper and lower bounds,Mathematics | Journal | 24 |
Issue | ISSN | Citations |
3 | 0095-8956 | 2 |
PageRank | References | Authors |
0.71 | 1 | 1 |
Name | Order | Citations | PageRank |
---|---|---|---|
D.T. Busolini | 1 | 4 | 1.91 |