¿Puede la contracción de una arista aumentar el número cromático en más de uno?

Question

Cuando se toma un ciclo uniforme, $C_{2n}$ contrayendo una arista aumenta el número cromático en $1$ .

¿Puede la contracción de una arista aumentar el número cromático en más de uno?

Answer 1

Supongamos que la arista $v_1v_2$ se contrata a $v_3$ y $v_1$ originalmente conectado al conjunto de vértices $S_1$ , $v_2$ originalmente conectado a $S_2$ .

En $v_1v_2$ se contrae $v_3$ está conectado a $S_1 \cup S_2$ y nada más que $\{v_3\}\cup S_1 \cup S_2$ ha cambiado la conectividad. Así que si damos $v_3$ un nuevo color que no estaba originalmente en el gráfico, nos hará el truco y por lo tanto no es posible que necesitemos dos nuevos colores.

Answer 2

Yo diría que no. Ahora tengo que ir a dar una clase pero creo que la prueba sería algo así:

Tomar una coloración válida del grafo inicial, contraer una arista entre vértices $v_0$ y $v_1$ y dar el vértice resultante de fusionar $v_0$ y $v_1$ el color $v_0$ tenía en la coloración inicial. Si esta coloración no es válida, entonces tiene que haber un vecino de $v_1$ que tenía el mismo color que $v_0$ . Coloreando cada uno de estos vértices (es decir, cada vecino de $v_1$ que tiene el mismo color que $v_0$ ) con un nuevo color, obtenemos una coloración válida del grafo contraído.

Como se trata de un método que nos permite crear una coloración válida a partir de cada coloración válida del grafo inicial añadiendo sólo un color, el número cromático del grafo contraído es como máximo el número cromático del grafo inicial más $1$ .

Answer 3

Sea $G$ sea un grafo con número cromático $k$ entonces $k = \min \{n\in \mathbb{N}\mid P(G,n) \neq 0\}$ donde $P(G,n)$ es el polinomio cromático.

Si al contraer el borde $uv$ el polinomio cromático aumenta en más de uno, entonces $P(G/uv,k+1) = 0$ . En $P(G-uv,k+1) = P(G/uv,k+1) + P(G,k+1)$ se deduce que $P(G-uv,k+1) = P(G,k+1)$ es decir, el borde $uv$ no crea ninguna restricción en la coloración del polinomio con $k+1$ colores.

Esto significa que el gráfico es tal que para cualquier $k+1$ -coloración del gráfico $G-uv$ el vértice $u$ y el vértice $v$ tienen asignados colores diferentes.

Pero podemos crear un $k+1$ -coloración del gráfico $G-uv$ tal que $u$ y $v$ comparten un color de la siguiente manera:

Toma el $k$ -coloración del gráfico $G$ y aplicarlo a $G-uv$ . Colorea cualquier vértice conectado a $u$ que comparte color con $v$ con el nuevo color. Ahora color $u$ con el mismo color que $v$ .

Por lo tanto, dicho gráfico no existe.