¿Razones por las cuales una gráfica puede no ser

Mientras razonaba un poco sobre esta pregunta , he tratado de identificar todas las diferentes razones por las cuales un gráfico puede no ser k colorable. Estas son las dos únicas razones que pude identificar hasta ahora:$G = (V_G,E_G)$$k$

1. contiene una camarilla de tamaño k + 1 . Esta es la razón obvia.$G$$k+1$

2. Existe un subgrafo de G de manera que ambas afirmaciones son ciertas:$H = (V_H, E_H)$$G$

   • no es k - 1 colorable.$H$$k-1$
   • . En otras palabras, existe un nodo x en G pero no en H , de manera que x está conectado a cada nodo en H .$\exists x \in V_G - V_H\ \forall y \in V_H\ \{x,y\} \in E_G$$x$$G$$H$$x$$H$

Podemos ver las 2 razones anteriores como reglas. Al aplicarlos de forma recursiva, las únicas 2 formas de construir un gráfico no coloreable que no contenga una camarilla k + 1 son:$k$$k+1$

1. Comience desde un ciclo de longitud par (que es coloreable), luego aplique la regla 2 para k - 1 veces. Tenga en cuenta que un borde no se considera un ciclo de longitud 2 (de lo contrario, este proceso tendría el efecto de construir una camarilla k + 1 ).$2$$k-1$$2$$k+1$
2. Comience desde un ciclo de longitud impar (que es coloreable), luego aplique la regla 2 para k - 2 veces. La duración del ciclo de inicio debe ser mayor que 3 (de lo contrario, este proceso tendría el efecto de construir una camarilla k + 1 ).$3$$k-2$$3$$k+1$

Pregunta

¿Hay alguna otra razón, aparte de los 2 anteriores, que hace un no gráfico plausible?$k$

$\ $
Actualización 30/11/2012

Más precisamente, lo que necesito es algún teorema de la forma:

Un gráfico tiene un número cromático χ ( G ) = k + 1 si y solo si ...$G$$\chi(G) = k + 1$

El cálculo de Hajós , señalado por Yuval Filmus en su respuesta, es un ejemplo perfecto de lo que estoy buscando, ya que un gráfico tiene un número cromático χ ( G ) = k + 1 si y solo si puede derivarse del axioma K k + 1 aplicando repetidamente las 2 reglas de inferencia del cálculo. El número de Hajós h ( G ) es el número mínimo de pasos necesarios para derivar$G$$\chi(G) = k + 1$$K_{k+1}$$h(G)$ (es decir, es la longitud de la prueba más corta).$G$

Es muy interesante que:

• La cuestión de si existe un gráfico cuya h ( G ) es exponencial en el tamaño de $G$$h(G)$$G$ todavía está abierta.
• Si tales no existe, entonces N P = c o N P .$G$$NP = coNP$

Deberías consultar el cálculo de Hajós . Hajós demostró que cada gráfico con número cromático al menos tiene un subgráfico que tiene una "razón" para requerir k colores. La razón en cuestión es un sistema de prueba para requerir k colores. El único axioma es K k , y hay dos reglas de inferencia. Vea también este documento de Pitassi y Urquhart sobre la eficiencia de este sistema de prueba.$k$$k$$k$$K_k$

Una respuesta parcial, ya que no conozco una buena "razón" que se pueda generalizar, pero el siguiente gráfico (desvergonzado mordido desde aquí ):

No es de 3 colores, pero obviamente es de 4 colores (es plano), y no contiene $K_{4}$ , ni ningún ciclo con un vértice adicional conectado a todos los vértices del ciclo (a menos que me falte algo, pero los únicos vértices conectado a un vértice y su vecino están en los 3 ciclos). Yendo más lejos, podría aplicar una versión de la regla 2 para obtener una gráfica del número cromático 5.

Sospecharía que para cualquier género dado, hay un gráfico de un cierto número cromático mínimo (vea la conjetura de Heawood ) que no sigue las reglas 1 o 2. Por supuesto, no tengo otra prueba que la intuición.

Lovasz encontró obstrucciones topológicas para k-colorabilidad y usó su teoría para resolver la conjetura de Knaser. Su teorema es el siguiente. Sea G un gráfico conectado, y sea N (G) un complejo simplicial cuyas caras son subconjuntos de V que tienen vecinos comunes. Entonces, si N (K) está conectado a k (es decir, todos sus grupos de homología reducida son 0 hasta la dimensión k-1), entonces el número de colores necesarios para colorear G es al menos k + 3.

No tener un gran conjunto independiente puede ser tan importante como tener una gran camarilla.

Una obstrucción importante para que un gráfico no sea k-colorable es que el tamaño máximo de un conjunto independiente es menor que n / k, donde n es el número de vértices. Esta es una obstrucción muy importante. Por ejemplo, implica que un gráfico aleatorio en G (n, 1/2) tiene un número cromático al menos n / log n.

Una obstrucción más refinada es que para cada asignación de pesos no negativos para los vértices no hay un conjunto independiente que capture una fracción de 1/5 (o más) del peso total. Tenga en cuenta que esto también incluye las "obstrucciones sin camarilla". La dualidad LP le dice que esta obstrucción es equivalente a que el "número cromático fraccional" de G sea mayor que k.

También hay obstáculos para la colorabilidad k de una naturaleza diferente que a veces van más allá de la barrera del número cromático fraccional. Les dedicaré una respuesta por separado.

$G$$\chi(G)=k+1$

$G$$\chi(G)\ge k$$G$$k-1$