¿Puede un gráfico ser no tricolor sin tener k4 como subgráfico?

Question

Tal y como plantea la pregunta, ¿es posible que un grafo tenga un número cromático mayor que tres sin que tenga como subgrafo un grafo completo de 4 vértices?

Answer 1

He aquí un simple contraejemplo con 6 vértices. Tomemos un ciclo de 5 $C_5$ . Añadir un nuevo vértice $A$ y conectarlo mediante una arista con cada vértice de $C_5$ . El gráfico resultante no es tricolorable. Si fuera tricolor, entonces $C_5$ sería bicolor, y no lo es.

Answer 2

Creo que este es el ejemplo al que se refiere Jeremy Hurwitz (el "squash" correspondiente a los vértices 4,5,6,7)

Answer 3

Un contraejemplo no constructivo proviene de un teorema de Erdős: Para cualquier $\chi$ y $g$ existen grafos de número cromático al menos $\chi$ y la circunferencia al menos $g$ . Si elegimos $g=\chi = 4$ entonces existe un gráfico que no es $3$ -colorable y está libre de triángulos y, por tanto, no puede contener un $K_4$ sub-gráfico.

Answer 4

Dejemos que $G$ sea un cuadrado con una diagonal. Obsérvese que los vértices opuestos deben tener el mismo color en cualquier coloración de 3. Por lo tanto, podemos utilizar este artilugio para sustituir cualquier vértice de un grafo sin cambiar su tricoloración.

Así, por ejemplo, podemos tomar $K_4$ y sustituir un vértice por $G$ (conecta dos de los bordes a una esquina y el tercer borde a la otra esquina).

Probablemente haya un contraejemplo más pequeño.