An Anti-Ramsey Theorem on Diamonds |
| |
| Authors: | J J Montellano-Ballesteros |
| |
| Institution: | 1. Instituto de Matemáticas, UNAM, Circuito Exterior, Ciudad Universitaria, Mèxico, DF, 04510, Mexico
|
| |
| Abstract: | Let G be the diamond (the graph obtained from K
4 by deleting an edge) and, for every n ≥ 4, let f(n, G) be the minimum integer k such that, for every edge-coloring of the complete graph of order n which uses exactly k colors, there is at least one copy of G all whose edges have different colors. Let ext(n, {C
3, C
4}) be the maximum number of edges of a graph on n vertices free of triangles and squares. Here we prove that for every n ≥ 4,
|
ext(n, {C3, C4})+ 2 ￡ f(n,G) ￡ ext(n, {C3,C4})+ (n+1).{\rm {ext}}(n, \{C_3, C_4\})+ 2\leq f(n,G)\leq {\rm {ext}}(n, \{C_3,C_4\})+ (n+1). |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
|
