- Tytuł:
- Almost-Rainbow Edge-Colorings of Some Small Subgraphs
- Autorzy:
-
Krop, Elliot
Krop, Irina - Powiązania:
- https://bibliotekanauki.pl/articles/30097998.pdf
- Data publikacji:
- 2013-09-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
Ramsey theory
generalized Ramsey theory
rainbow-coloring
edge-coloring
Erdös problem - Opis:
- 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 $ f(n, 5, 0) \ge \frac{7}{4} n - 3 $, slightly improving the bound of Axenovich. We make small improvements on bounds of Erdös and Gyárfás by showing $ \frac{5}{6} n + 1 \leq f(n,4,5) $ and for all even $ n ≢ 1(\text{mod } 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 ⊆ G $ is colored by at least three colors. This improves the best known upper bound of Axenovich, Füredi, and Mubayi.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2013, 33, 4; 771-784
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł