El número de cruce 2-coloreado

Ponente(s): Ruy Fabila Monroy

Sea $G$ una gráfica y $D$ un dibujo simple de $G$ en el plano. Sea $cr(D)$ el número de pares de aristas de $D$ que se cruzan. Sea $\chi$ una dos coloración de las aristas de $D$. Sea $cr_\chi(G)$ el número de aristas de $D$ del mismo color que se cruzan. En esta plática nos interesa la razón $\cr_\chi(G)/\cr(G)$, es fácil ver que existe una coloración donde este valor es a lo más 1/2. Veremos que para gráficas densas existe una constante $c>0$ y una coloración $\chi$ tal que $\cr_\chi(G)/\cr(G) \le 1/2-c$,