Almost-rainbow edge-colorings of some small subgraphs

Elliot Krop; Irina Krop

paper

Almost-rainbow edge-colorings of some small subgraphs

arXiv:0803.0572

Abstract

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 the {7/4}n-3 $, s l i g h tl y im p r o v in g t h e b o u n d o f A x e n o v i c h . W e mak es ma l l im p r o v e m e n t so nb o u n d so f E r d o ˝ s an d G y a ˊ r f a ˊ s b y s h o w in g$ {5/6}n+1\leq f(n,4,5) $an df or a l l e v e n$ n\not\equiv 1 \pmod 3 $,$ f(n,4,5)\leq n-1 $. F or a co m pl e t e bi p a r t i t e g r a p h$ G=K_{n,n} $, w es h o w ann - co l or co n s t r u c t i o n t oco l or t h ee d g eso f$ G $so t ha t e v er y$ C_4\subseteq G$ is colored by at least three colors. This improves the best known upper bound of M. Axenovich, Z. Füredi, and D. Mubayi.

13 pages