los problemas de Nordhaus-Gaddum para el número cromático del gráfico y su complemento

Question

¿Existe alguna relación entre el número cromático de un gráfico $G$ y su complemento $G'$ que siempre son ciertas?

He visto estos: $\chi(G)\chi(G')\geq n$ y $\chi(G)+\chi(G')\geq 2n$ ,

pero no estoy muy seguro de ellos.

Answer 1

La siguiente prueba está tomada de Graphs and Digraphs de Chartrand, Lesniak y Zhang, que atribuyen la prueba a Hudson V. Kronk.

Dejemos que $G$ sea un gráfico tal que $V(G)=n$ . Supongamos que $\chi(G)=k$ y $\chi(\overline{G})=l$ . Supongamos que nos dan un $k$ -coloración $c$ y $l$ -coloración $\overline{c}$ de $G$ y $\overline{G}$ respectivamente. Con estas coloraciones, se puede obtener una coloración de $K_n$ . A cada vértice $v$ de $G$ (y también $\overline{G}$ ) se asocia el par ordenado $\{c(v),\overline{c}(v)\}$ . Dados los distintos vértices $v$ y $w$ en $K_n$ se observa que $v$ y $w$ deben ser adyacentes en $G$ o $\overline{G}$ , por lo que se obtiene una coloración de $K_n$ utilizando como máximo $kl$ colores. Por lo tanto,

$$\chi(K_n)=n\leq kl=\chi(G)\cdot \chi(\overline{G}).$$

Para demostrar $\chi(G)+\chi(\overline{G})\leq n+1$ utilizamos el siguiente lema:

Lema : Para cada gráfico $G$

$$\chi(G)\leq 1+\operatorname{max}\{\delta(H)\},$$

donde $H$ es un subgrafo de $G$ y el máximo se toma sobre todos los subgráficos $H$ de $G$ .

Dejemos que $q=\operatorname{max}\{\delta(H)\}$ . Entonces, por el lema anterior, tenemos $\chi(G)\leq 1+q$ . A continuación determinamos $\operatorname{max}\{\delta(\overline{G})\}$ que reclamo es $n-q-1$ . Supongamos lo contrario. Entonces existe un subgrafo $H$ de $G$ tal que $\delta(\overline{H})\geq n-q$ . Esto implica que cada vértice de $H$ tiene un grado menor o igual a $q-1$ . Sea $K$ sea un subgrafo de $G$ tal que $\delta(K)=q$ (nótese que dicho subgrafo existe ya que $q=\operatorname{max}\{\delta(H)\}$ ). Es evidente que ningún vértice de $K$ está en $H$ . Ahora, $|V(K)|\geq q+1$ desde $\delta(K)=q$ , lo que implica

$$|V(H)|\leq n-(q-1)=n-q-1,$$

contradiciendo el hecho $\delta(\overline{H})\geq n-q$ . Por lo tanto, $\operatorname{max}\{\delta(\overline{G})\}\leq n-q-1$ lo que implica por el lema que $\chi(\overline{G})\leq 1+(n-q-1)=n-q$ . La combinación de todo esto da como resultado

$$\chi(G)+\chi(\overline{G})\leq (1+q)+(n-q)=n+1.$$

Más relaciones entre el número cromático de un gráfico y su complemento son:

• $2\sqrt{n}\leq \chi(G)+\chi(\overline{G})$

• $\chi(G)\cdot \chi(\overline{G})\leq (\frac{n+1}{2})^2$

Answer 2

$(a)$ Demostrar que $\chi(G)\cdot \chi(G')\geq n$ .

Prueba: Para todo gráfico $G$ y $G'$ sabemos que $\chi(G)\geq {n\over \alpha(G)}$ y $\chi(G')\geq \omega(G')=\alpha(G)$ donde $\alpha(G)$ y $\omega(G)$ denotan el número de independencia y el número de camarilla de $G$ . Así que $\chi(G)\cdot \chi(G')\geq {n\over \alpha(G)}\cdot \alpha(G)=n$ . Así, $\chi(G)\cdot \chi(G')\geq n$ .

$(b)$ Demostrar que $\chi(G)+\chi(G')\geq 2\sqrt{n}$ .

Prueba: Dado que ambos $\chi(G)$ y $\chi(G')$ son al menos una sabemos que $(\chi(G)-\chi(G'))^2\geq 0$ y así $\chi(G)^2-2\chi(G)\cdot \chi(G')+\chi(G')^2\geq 0$ . Añadiendo $4\chi(G)\cdot \chi(G')$ a ambos lados de la ecuación obtenemos $\chi(G)^2+2\chi(G)\cdot\chi(G')+\chi(G')^2\geq 4\chi(G)\cdot\chi(G')$ y factorizando el lado izquierdo tenemos ahora $(\chi(G)+\chi(G'))^2\geq 4\chi(G)\cdot\chi(G')$ . Tomando la raíz cuadrada de ambos lados nos da $\chi(G)+\chi(G')\geq 2\sqrt{\chi(G)\cdot \chi(G')}$ y como $\chi(G)\cdot \chi(G')\geq n$ por el resultado anterior en $(a)$ podemos concluir que $\chi(G)+\chi(G')\geq 2\sqrt{n}$ .

Answer 3

En realidad no estás del todo en lo cierto. así que tu inplicación de que cada vértice de H tiene grado menor o igual a q - 1 no es cierta. mientras uno de ellos tenga grado menor o igual a q - 1, el grado del gráfico del complemento sería igual a n - q.