Me han hecho esta pregunta hace unos meses aquí. He recibido una respuesta de la que voy a explicar, pero se encontró un error en la prueba. Estoy buscando nuevas respuestas, o una manera de corregir uno que ha sido propuesto.
Enunciado del problema:
Dado un grafo $G(V,E)$, vamos a $\chi(G)$ ser su cromática número, y $\chi_1(G)$ $1$- inadecuado cromática número (lo que significa que cada nodo puede tener en la mayoría de $1$ vecino con el mismo color; o de otra manera de mirar esto es que la cromática número permanece sin cambios si cualquier la coincidencia es eliminado de $G$).
Si un gráfico de $G$ satisface $\chi_1=\chi$, ¿cuántas aristas debe $G$ tiene (al menos) ?
Comentarios:
Dibujos rápidos sugieren que el número de aristas debe ser mayor que $2(\chi-1)^2\in \mathcal{O}(\chi^2)$, pero no puedo manejar para demostrarlo.
También es fácil ver que el número de aristas debe ser mayor que $\chi(\chi-1)\in \mathcal{O}(\chi^2)$. De hecho, extremal la teoría nos dice que el número de aristas de un grafo es siempre mayor que $\chi(\chi-1)/2$, pero si podemos eliminar cualquier coincidencia, tiene que ser más grande que la de $\chi(\chi-1)$.
Es bastante fácil demostrar (por ejemplo, por inducción) que un gráfico que satisface $\chi_1=\chi$ tiene al menos $2\chi-1$ vértices.
Resumen de la respuesta aquí:
@Deedlit el intento puede resumirse de la siguiente manera: Considere la posibilidad de un gráfico de $G$$\chi_1=\chi$, y deje $m_{ij}$ el número de aristas entre dos clases de color $i,j \in \{1,\cdots,\chi\}$. Es suficiente para demostrar que $$ m_{ij}\ge 4 $$ para todos los pares de clases de color $i,j$ excepto uno, digamos de clase de color $k$, por lo que $$ m_{kj}\ge 2 $$
Dado que entre un total de $\chi-1$ clases de color, hay $\binom{\chi-1}{2}$ maneras de seleccionar un par de ellos, y $\binom{\chi-1}{1}$ de la selección de $1$, el número total de aristas verifica: $$ \boxed{ m\ge 4\binom{\chi-1}{2}+2\binom{\chi-1}{1}=2(\chi-1)^2 } $$
Más detalles sobre la prueba, y donde está mal:
Demostrando que $m_{ij}\ge 2$ para todos los pares es sencillo: si sólo hay $1$ borde entre dos clases de color de todas las coincidencias que se retira y que contiene esta ventaja podría permitir la fusión de estas dos clases, contradiciendo $\chi_1=\chi$. Demostrando $m_{ij}\ge 4$ con excepción de un par es más complicado. Deedlit considera un par de $i,j$ que $m_{ij}<4$ y mostró que todos los otros pares no puede tener tan poco los bordes. Él rompió el problema a cuatro casos posibles:
Para cada uno de estos casos, Deedlit afirma que si alguno de los nodos de $x,z,y$ tomó un color diferente diferente de $i,j$, entonces los vértices $a,b$ podría tomar otro color, así como para mantener un $1$-inadecuado para colorear. Pero por nuestra suposición, es imposible eliminar un color. Por lo tanto, los nodos $x$ $y$ debe necesariamente mantener el color de $j$, es decir, no son necesariamente más de $4$ bordes entre el color de la clase $j$ y todos los demás, excepto, para a $i$.
Por ejemplo, en el caso de $1$ si $x$ es de color $k$, de los vértices de la clase de color $i$ todos podemos tomar color $j$, disminuyendo $\chi$ por una unidad. Siendo esto imposible, $x$ no puede tomar el color de $k$, es decir, $x$ está vinculado a todas las otras clases (excepto $i$) con al menos $2$ bordes. Lo mismo vale para los $y$.
En el caso de $3$ si $x$ es de color $k$, $a$ puede tomar el color de $k$ demasiado, y todos los otros vértices de la clase de color $i$ puede tomar el color de $j$. Aquí es donde esto está mal: esto no implica que hay al menos $2$ bordes de $x$ a todas las otras clases: no podría ser simplemente un nodo $v$ en la clase de color $k$ con bordes $(v,a)$, $(v,x)$.
Creo Deedlit el enfoque es bueno. Hace un montón de sentido y estoy convencido de que la última ecuación de (la caja) es correcta. Pero la prueba de que hay que arreglar.
Cualquier otro enfoque es bienvenida.
