Dado un gráfico en $n$ vértices encontrar la máxima cantidad de aristas para que pueda ser coloreado sin monocromo $K_m$

Question

He inventado un problema y quería compartirlo :¿Cuál es la máxima cantidad de aristas que tiene un gráfico en $n$ vértices puede tener si se puede colorear el borde con $k$ colores para que no tenga un aspecto monocromático $K_m$ ?

Creo que tengo una solución, me gustaría una verificación. Las generalizaciones también serían muy apreciadas.

Muchas gracias de antemano.

Saludos.

Answer 1

Dicho grafo no puede contener un subgrafo completo de tamaño $R\underbrace{(m,m\dots m)}_{\text{k times}}=j$ . ¿Cuál es el subgrafo en $n$ vértices que tiene el mayor número de aristas y no contiene un suógrafo completo de tamaño $n$ ? Es el gráfico de Turan $T(n,j-1)$ Así que si $T(n,j-1)$ trabajos que hemos hecho.

Por la definición del número de Ramsey $K_{j-1}$ admite una coloración $C$ con $k$ colores y no monocromática $K_m$ . Así que lo que hacemos es tomar $T(n,j-1)$ y asumir cada uno de los $j-1$ partes de $T(n,j-1)$ es un vértice en $K_{j-1}$ . Así, dados dos vértices adyacentes de $T(n,j-1)$ coloreamos ese borde usando el color utilizado en $C$ para conectar los vértices de sus partes correspondientes (Ya que cada parte de $T(n,j-1)$ se ve como un vértice de $K_{j-1}$ . Esta coloración no nos da ninguna monocromática $K_m$ porque si tenemos $m$ vértices que están todos conectados por pares deben estar todos en partes diferentes, y entonces los colores de las aristas entre ellos serán los mismos que el color de las aristas entre los vértices en $K_{j-1}$ con la coloración $C$ .

Por lo tanto, el número máximo de aristas es el número de aristas en el $T(n,j-1)$ que es $\lfloor\frac{(j-2)n^2}{2(j-1)}\rfloor$ . También se deduce de Turan que el gráfico es único.