Mean Ramsey-Turán numbers
| dc.creator | Yuster, Raphael | |
| dc.date | 2004-08-09 | |
| dc.date.accessioned | 2026-07-07T05:11:07Z | |
| dc.date.available | 2026-07-07T05:11:07Z | |
| dc.description | A $ρ$-mean coloring of a graph is a coloring of the edges such that the average number of colors incident with each vertex is at most $ρ$. For a graph $H$ and for $ρ\geq 1$, the {\em mean Ramsey-Turán number} $RT(n,H,ρ-mean)$ is the maximum number of edges a $ρ$-mean colored graph with $n$ vertices can have under the condition it does not have a monochromatic copy of $H$. It is conjectured that $RT(n,K_m,2-mean)=RT(n,K_m,2)$ where $RT(n,H,k)$ is the maximum number of edges a $k$ edge-colored graph with $n$ vertices can have under the condition it does not have a monochromatic copy of $H$. We prove the conjecture holds for $K_3$. We also prove that $RT(n,H,ρ-mean) \leq RT(n,K_{χ(H)},ρ-mean)+o(n^2)$. This result is tight for graphs $H$ whose clique number equals their chromatic number. In particular we get that if $H$ is a 3-chromatic graph having a triangle then $RT(n,H,2-mean) = RT(n,K_3,2-mean)+o(n^2)=RT(n,K_3,2)+o(n^2)=0.4n^2(1+o(1))$. | |
| dc.description | 9 pages | |
| dc.identifier | https://arxiv.org/abs/math/0408108 | |
| dc.identifier | http://arxiv.org/abs/math/0408108 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/72137 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C35; 05C15; 05C55 | |
| dc.title | Mean Ramsey-Turán numbers | |
| dc.type | text |