Dejemos que $G$ sea un gráfico con n vértices. Demostrar que $\chi(G)\cdot\chi(\overline G)\geqslant n$ .
Sé que el número cromático de un gráfico con $n$ los vértices tendrán entre $\chi(G-\ni) \leqslant\chi(G)\leqslant\ni(G-v)+1$ y también que el límite superior del número cromático será mayor o igual al grado máximo de un vértice en $G+1$ y que el límite inferior es el mayor o igual a la mayor camarilla.
¿Hay algo que podamos hacer con esta información para demostrar nuestra propuesta?
Bien, supongamos que tenemos un gráfico completo en $n$ vértices. Entonces, como cada vértice es adyacente a todos los demás vértices del gráfico, no podemos utilizar un color más de una vez. Así que obtenemos un $n$ -coloración en el gráfico completo. En un grafo completo, el complemento sería un conjunto independiente de $n$ vértices, cada uno para poder ser coloreado con un solo color. ¿Es esto lo que queremos hacer?
No entiendo lo que has dicho. Lo que queremos demostrar es que si tenemos un $a$ -coloración de $G$ y un $b$ -coloración de $\overline{G}$ entonces $ab \geq n$ . Esto se debe a que $\chi(G)$ es el mínimo de tales $a$ y $\chi(\overline{G})$ es el mínimo de tales $b$ . Así que $\chi(G) \chi(\overline{G})$ es el valor mínimo de $ab$ y queremos demostrar que este valor nunca es menor que $n$ . Además, el gráfico completo en $n$ vértices proviene de la unión de $G$ y $\overline{G}$ .
@JohnLocke Ah, he entendido lo que has dicho. No, no es ese tipo de razonamiento el que queremos hacer. El objetivo es demostrar que para cada $a$ -coloración de $G$ y cada $b$ -coloración de $\overline{G}$ tenemos $ab \geq n$ .
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
1 votos
¿Qué es? $\overline{G}$ ?
0 votos
El complemento de G