Almost-rainbow edge-colorings of some small subgraphs

Details Almost-rainbow edge-colorings of some small subgraphs Almost-rainbow edge-colorings of some small subgraphs

2008-03-04

arxiv.org/abs/0803.0572v2

Mathematics

Combinatorics

9 pages

Scientific paper

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$, slightly improving the bound of Axenovich. We make small improvements on bounds of Erd\H os and Gy\'arf\'as by showing ${5/6}n+1\leq f(n,4,5)$ and for all even $n\not\equiv 1 \pmod 3$, $f(n,4,5)\leq n-1$ . For a complete bipartite graph $G=K_{n,n}$, we show an n-color construction to color the edges of $G$ so that every $C_4\subseteq G$ is colored by at least three colors. This improves the best known upper bound of M. Axenovich, Z. F\"uredi, and D. Mubayi.

Affiliated with

Also associated with

No associations

Rating

Almost-rainbow edge-colorings of some small subgraphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Almost-rainbow edge-colorings of some small subgraphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Almost-rainbow edge-colorings of some small subgraphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-160530