Un grafo cuyo cada ciclo impar es un triángulo es 4-colorable

Question

Como dice el título, tengo un grafo finito simple cuyo cada ciclo impar es un triángulo, y quiero demostrar que $\chi (G)\leq 4$ .

Mi idea era intentar utilizar el hecho de que un grafo es bipartito si no contiene ciclos Impares. La dirección general era: si de alguna manera "eliminamos" los triángulos, obtenemos un grafo de 2 colores, y entonces tal vez de alguna manera podemos añadirlos de nuevo sin añadir más de 2 colores necesarios...?

Answer 1

Sea $G=(V,E)$ sea un grafo finito en el que cada ciclo impar es un triángulo. Podemos suponer que $G$ es un contraejemplo mínimo, de modo que todo subgrafo propio de $G$ es $4$ -colorable, y $G$ es un grafo simple conexo. Elige un vértice raíz $u.$

Sea $V_i=\{v\in V:d(u,v)\equiv i\pmod2\}.$ Si ambos subgrafos inducidos $G|V_1$ y $G|V_2$ son $2$ -colorable, hemos terminado; así que podemos suponer que uno de ellos contiene un ciclo impar, que debe ser un triángulo. Es decir, $G$ contiene un triángulo $T$ con $V(T)=\{v_1,v_2,v_3\}$ donde $d(u,v_1),\ $$ d(u,v_2), $ and $ d(u,v_3)$ tienen todos la misma paridad.

Tenga en cuenta que $u\notin V(T),$ y un camino más corto desde $u$ a $v_i$ no contiene ninguna arista o vértice de $T$ excepto $v_i.$ Por lo tanto, existe un camino $P$ de $v_1$ a $v_2$ que no contiene ninguna arista o vértice de $T$ excepto $v_1$ y $v_2.$ El camino $P$ debe tener longitud $\ge2,$ pero si $P$ tenía longitud $\ge3$ entonces añadiendo uno o dos bordes de $T$ obtendríamos un ciclo impar de longitud $\ge5,$ por lo que la longitud de $P$ es exactamente $2.$ Es decir, hay un vértice $w\notin V(T)$ que es adyacente a $v_1$ y $v_2.$

Del mismo modo, existe un vértice $w'\notin V(T)$ que es adyacente a $v_2$ y $v_3.$ Pero si tuviéramos $w\ne w'$ entonces tendríamos un $5$ -ciclo $v_1,w,v_2,w',v_3,v_1$ en $G.$ Por lo tanto $w=w'$ es adyacente a los tres vértices de $V(T).$ Sea $v_4=w=w';$ entonces el subgrafo inducido $Q=G|\{v_1,v_2,v_3,v_4\}$ es un $K_4.$

El subgrafo $G'=G-E(Q)$ es $4$ -colorable. Obsérvese que los vértices $v_1,v_2,v_3,v_4$ se encuentran en cuatro componentes diferentes de $G';$ pues, si $v_i$ y $v_j$ ( $i\ne j$ ) estaban conectadas por un camino en $G',$ entonces habría un ciclo impar de longitud $\ge5$ en $G.$ Por lo tanto, en $4$ -colorear $G',$ los colores de esos cuatro vértices pueden asignarse arbitrariamente; nosotros les damos colores diferentes, de modo que la coloración de $G'$ será también una coloración propia de $G.$

Este argumento demuestra que un finito gráfico, en el que cada ciclo impar es un triángulo, es $4$ -colorable. Por el Teorema de Erdos-De Bruijn lo mismo ocurre con los grafos infinitos.