# zbMATH — the first resource for mathematics

Almost-rainbow edge-colorings of some small subgraphs. (English) Zbl 1295.05151
Summary: 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 Erdős and Gyárfás. We show that $$-3f(n, 5, 9)\geq \frac{7}{4} n$$, slightly improving the bound of M. Axenovich [Discrete Math. 222, No. 1–3, 247–249 (2000; Zbl 0969.05042)]. We make small improvements on bounds of P. Erdős and A. Gyárfás [Combinatorica 17, No. 4, 459–467 (1997; Zbl 0910.05034)] by showing $$\frac{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 et al. [J. Comb. Theory, Ser. B 79, No. 1, 66–86 (2000; Zbl 1023.05101)].

##### MSC:
 05C55 Generalized Ramsey theory 05C15 Coloring of graphs and hypergraphs 05C38 Paths and cycles
Full Text: