ALMOST-RAINBOW EDGE-COLORINGS OF SOME SMALL SUBGRAPHS

作者：Krop Elliot^*; Krop Irina

来源：Discussiones Mathematicae - Graph Theory, 2013, 33(4): 771-784.

DOI：10.7151/dmgt.1710

• Ramsey theory
• generalized Ramsey theory
• rainbow-coloring
• edge-coloring
• Erdos problem

Let f (n, p, q) be the minimum number of colors necessary to color the edges of K-n so that every K-p is at least q-colored. We improve current bounds on these nearly "anti-Ramsey" numbers, first studied by Erdos and Gyarfas. We show that f (n, 5, 9) >= 7/4n - 3, slightly improving the bound of Axenovich. We make small improvements on bounds of Erdos and Gyarfas by showing 5/6n+1 <= f (n, 4,5) and for all even n not equivalent to 1 (mod 3), f (n, 4, 5) <= n-1. For a complete bipartite graph G = K-n,K-n show an n-color construction to color the edges of G so that every C-4 subset of G is colored by at least three colors. This improves the best known upper bound of Axenovich, Furedi, and Mubayi.

• 出版日期2013