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)].

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