gráfico plano y número cromático

Question

Así que esta pregunta me está haciendo polvo en serio.

Dejemos que $G$ se dibuje en el plano de manera que satisfaga:

1. El límite de la región infinita es un ciclo $C$
2. Todas las demás regiones tienen un ciclo límite de longitud $3$
3. Cada vértice de $G$ no en $C$ tiene un grado parejo

Demuestra que $\chi(G) \le 3$ , donde $\chi(G)$ es el número cromático.

Sé que tengo que usar la inducción y considerar dos casos para el primer paso: Si algunos dos vértices no consecutivos de $C$ son adyacentes y en el segundo caso eliminaría una arista de $C$ y aplicar la hipótesis de inducción.

¿Alguien puede ayudar?

Answer 1

Esto surgió en CS Theory hace un tiempo: https://cstheory.stackexchange.com/questions/4027/coloring-planar-graphs

Lamentablemente, algunos de los enlaces de ese post están muertos / no son gratuitos.

Este documento demuestra un caso especial de lo que mencionas, que si todos los vértices son de grado par en una casi triangulación, entonces el grafo es tricolor. La clave está en que dicho grafo es euleriano, y por tanto tiene un recorrido euleriano que no se cruza con él. Colorear los vértices 1, 2, 3, 1, 2, 3, etc. a lo largo de este camino es una 3-coloración adecuada.

Para el caso de que $G$ tiene vértices Impares en su frontera, se puede construir una casi-triangulación euleriana plana $H$ tal que $G \subset H$ y $H$ es euleriano. Sea $C = v_1v_2\ldots v_x$ y supongamos $v_j$ y $v_k$ en $C$ son de grado impar. WLOG $k > j$ . Añadir vértices $u_ju_{j+1}\ldots u_{k-1}$ en la región exterior en el orden obvio. A continuación, añada los bordes $v_iu_i$ y $v_{i+1}u_i$ para $j \le i \le k-1$ . Ahora $u_j$ y $u_{k-1}$ son ambos de grado impar a menos que $j = k-1$ pero podemos repetir este proceso hasta que estos dos vértices Impares se resuelvan (ya que los vértices Impares siguen acercándose). Ahora tenemos menos vértices Impares, así que repitiendo este proceso podemos igualar todos los vértices.

Answer 2

Introducimos en $|E(G)|$ . El caso base es trivial.

Supongamos primero que hay dos vértices no consecutivos $u, v$ de $C$ que son adyacentes. Sea $e$ ser el borde que los une. Entonces, $e$ divide el gráfico en dos gráficos $G_1$ y $G_2$ a cada lado de $e$ en el plano, ambas satisfacen la hipótesis de inducción, por lo que $\chi(G_1), \chi(G_2) \leq 3$ . Permutando los colores de (digamos) $G_2$ adecuadamente para que $u$ y $v$ se colorean de forma idéntica en $G_1$ y $G_2$ obtenemos una 3-coloración de $G$ Así que $\chi(G) \leq 3$ .

En caso contrario, no hay dos vértices no consecutivos de $C$ son adyacentes. Sea $w_0, w_1$ sean cualesquiera vértices consecutivos en $C$ . Sabemos que hay un vértice $u \in V(G) - V(C)$ con $w_0 u, w_1 u \in E(G)$ . Por la hipótesis de inducción, el gráfico $G' = G \setminus w_0 w_1$ tiene $\chi(G') \leq 3$ . Afirmo que cualquier 3-coloración de $G'$ tiene $w_0$ y $w_1$ como colores diferentes, de modo que esta coloración se extiende a una 3-coloración de $G$ .

Supongamos que no, es decir $w_0$ y $w_1$ se colorean de forma idéntica, y $u$ se colorea de forma diferente. Consideremos los triángulos que inciden en $u$ con vértices $u w_i w_{i + 1}$ . Desde $u$ tiene grado par, entonces el camino $P = w_1 w_2 \ldots w_{\deg(u) - 1} w_0$ tiene una longitud impar. Nuestra 3-coloración de $G'$ determina que $P$ es de 2 colores, y un camino impar de 2 colores tiene extremos de colores opuestos (fácilmente verificable), lo cual es una contradicción.