Limitantes para o número de colorações das arestas de Kn que não possuem um K4-Rainbow.

Abstract

Given n,r ∈ N, this paper seeks non-trivial lower and upper bounds for the number of r-edge colorings, of the complete graph Kn, that avoid K4-rainbow (K4 colored in such a way that if an edge is colored with a color λ, another edge can’t be colored by λ) as a subgraph. We denote this number of colorings by c4(n,r) and prove that, if n ≥ 3, then c4(n,r) ≥ max{5(2n),r1+⌊n2 /4 ⌋. We also demonstrate that, fixed r > 5y, with y ≥ 10, for n large enough, c4(n,r) ≤ r ^Ä 1+o(1)+y−91 ä n2 /4 .