Reducir un grafo sin disminuir su número cromático

Question

Intentando encontrar un algoritmo para reducir un grafo sin bajar su número cromático, hice el siguiente algoritmo (pero no estoy seguro de que funcione):

1. Dado un grafo (simple) $G$ buscar subgrafos de $m$ ( $m \geq 2$ ), que son isomorfos a $K_m$ menos una arista, y cuya arista sin rellenar (digamos, $e=(v_1,v_2)$ ) sigue sin rellenarse en $G$ es decir $e\not\in E(G)$ . Elija un subgrafo con el máximo $m$ y, a continuación, identificar $v_1$ y $v_2$ . Tras reducir algunas aristas múltiples a aristas simples, obtenemos un nuevo grafo simple $G'$ cuyo número de vértices es uno menos que el de $G$ .
2. Repite #1 hasta que no haya tal subgrafo.

Llamemos a este algoritmo "Highest dimension first folding (HDFF)". Me pregunto si HDFF siempre nos da $K_{\chi(G)}$ donde $\chi(G)$ es el número cromático de $G$ y $K_n$ es el grafo completo de $n$ vértices.

Answer 1

Lo he descubierto. Su algoritmo no preserva el número cromático (sin embargo, no puede bajar el número cromático) y esta vez he encontrado una razón correcta.

Considera el gráfico, $G$ . Los vértices $v_1, v_2, x_1, x_2$ de $G$ crear un $K_4$ con el borde entre $v_1$ y $v_2$ desaparecida. El mayor $K_m - e$ en este gráfico tiene $m=3$ y uno viene dado por $x_1, x_2, v_1, v_2$ .

Aplicando (1) a este gráfico con $v_1$ y $v_2$ identificado produce un grafo con un $K_5$ subgrafo. Por lo tanto, tiene un número cromático de al menos 5. Sin embargo, $G$ tiene número cromático 4 como podemos ver en la coloración de la figura de $G$ .

Answer 2

Tu algoritmo dará como resultado un grafo completo, pero creo que no preserva el número cromático. El Gráfico de Grötzsch es el grafo más pequeño sin triángulos y con número cromático 4. El mayor subgrafo inducido del grafo de Grötzsch que es $K_m$ menos una arista tiene $m=3$ . Aplicando (1) de tu algoritmo a cualquier par de vértices no adyacentes del grafo de Grötzsch se obtendrá un grafo que no tiene triángulos y es más pequeño que el grafo de Grötzsch, por lo que tiene un número cromático diferente.

EDIT: Esto está mal. Hay triángulos en el gráfico resultante después de aplicar (1). Voy a mirar en esto un poco más tarde.