número cromático de un gráfico frente a su complemento

Question

Lo que se puede decir sobre la tasa de crecimiento de $f(n)$ definido por $$f(n) = \min_ {|V(G)|=n} \left [ \chi (G) + \chi ( \bar {G}) \right ],$$ donde el mínimo se toma sobre todos los gráficos $G$ en $n$ vértices.

Dos observaciones.

(1) O bien $G$ o $ \bar {G}$ contiene una camarilla en aproximadamente $ \log {n}$ vértices por la teoría de Ramsey, así que $f(n) \ge c_1 \log n $ por alguna constante $c_1 > 0$ .

(2) Si $G = G(n,1/2)$ es un gráfico aleatorio, entonces $ \chi (G) \approx \chi ( \bar {G}) \approx n / \log {n}$ casi seguro, así que también tenemos $f(n) \le c_2 \, n/ \log n$ por alguna constante $c_2 > 0$ .

Estos límites parecen irremediablemente lejanos.

¿Podemos mejorar los límites $$ c_1 \log n \le f(n) \le c_2 \, n / \log n$$ para todos los suficientemente grandes $n$ ?

Answer 1

Aunque ya hay una respuesta aceptada, respondo para dar un poco más de información, ya que lo que tengo que decir no encajaría en un comentario.

Este es el Teorema de Nordhaus-Gaddum:

Si $G$ es un gráfico de orden $n$ Entonces

1. $2 \sqrt {n} \leq \chi (G) + \chi ( \bar {G}) \leq n+1$
2. $n \leq \chi (G) \cdot \chi ( \bar {G}) \leq \left ( \frac {n+1}{2} \right )^2$

Y no hay ninguna mejora posible de ninguno de estos límites. De hecho, se puede decir mucho más:

Deje que $n$ ser un entero positivo. Por cada dos números enteros positivos $a$ y $b$ de tal manera que

1. $2 \sqrt {n} \leq a + b \leq n+1$
2. $n \leq a b \leq \left ( \frac {n+1}{2} \right )^2$

hay un gráfico $G$ de orden $n$ de tal manera que $ \chi (G) = a$ y $ \chi ( \bar {G}) = b$ .

Fuente: Graphs & Digraphs (Quinta edición) por Chartrand, Lesniak y Zhang

Answer 2

(Respondiendo para la posteridad, no seleccione esto como lo mejor.)

Primero, extender la prueba de @ccc para mostrar que si $pq \geq n$ entonces $f(n) \leq p+q$ . Lo haces primero tomando un gráfico sobre $n$ nodos que consisten en (a lo sumo) $p$ camarillas de a lo sumo $q$ cada uno de los nodos, y observando que $ \chi (G) \leq p$ y $ \chi ( \bar G) \leq q$ .

Ahora, como se muestra por ccc en los comentarios anteriores, $$ \lceil 2 \sqrt {n} \rceil \leq f(n) \leq 2 \lceil \sqrt {n} \rceil $$

Esto se reduce a un máximo de dos valores.

En general, si $ \lceil 2x \rceil < 2 \lceil x \rceil $ entonces la parte fraccionaria de $x$ está en $(0, \frac {1}{2})$ . Así que sólo tenemos que considerar los casos en los que la parte fraccionaria de $ \sqrt n$ está en este rango, es decir, $ \sqrt n =p + \delta $ donde $p$ es un número entero y $0< \delta < \frac {1}{2}$ .

Reclamar: $p(p+1) \geq n$ .

Sabemos que $p(p+1)+ \frac {1}{4}=(p+ \frac {1}{2})^2>(p+ \delta )^2=n$ . Desde $n$ y $p(p+1)$ son enteros, esto significa $p(p+1) \geq n$ .

Por lo tanto, $f(n) \leq 2p+1 = \lceil 2 \sqrt {n} \rceil $

Así que sabemos que $f(n)$ es siempre $ \lceil 2 \sqrt {n} \rceil $