Rainbow Cliques in Edge-Colored Graphs
| Autor: | Czygrinow, Andrzej, Molla, Theodore, Nagle, Brendan |
|---|---|
| Rok vydání: | 2024 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | Let $G = (V,E)$ be an $n$-vertex graph and let $c: E \to \mathbb{N}$ be a coloring of its edges. Let $d^c(v)$ be the number of distinct colors on the edges at $v \in V$ and let $\delta^c(G) = \min_{v \in V} \{ d^{c}(v) \}$. H. Li proved that $\delta^c(G) > n/2$ guarantees a rainbow triangle in $G$. We give extensions of Li's result to cliques $K_r$ for $r \ge 4$. Comment: 16 pages |
| Databáze: | arXiv |
| Externí odkaz: |
|